Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int d[2005];
- int mark[2005];
- int m[2005][2005];
- int t=0;
- int cit[2005];
- vector<vector<int> > vec;
- vector <int> r;
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- int n,p,q,s,f,v,a,b,w,e,k,c;
- cin >> n >> e >> k >> s;
- vec.resize(n+1);
- for(int i=1; i<=k; i++) cin >> cit[i];
- for(int i=1; i<=e; i++){
- cin >> a >> b >> c;
- vec[a].push_back(b);
- vec[b].push_back(a);
- m[a][b]=c;
- m[b][a]=c;
- }
- for(int i=1; i<=n; i++){
- d[i]=100000000;
- }
- d[s]=0;
- d[n+1]=100000000;
- for(int i=1; i<=n; i++){
- v=n+1;
- for(int i=1; i<=n; i++){
- if((d[i]<=d[v]) && (mark[i]==0)) v=i;
- }
- mark[v]=1;
- if(vec[v].size()>=1)
- for(int t=0; t<=vec[v].size()-1; t++){
- w=vec[v][t];
- d[w]=min(d[w], d[v]+m[v][w]);
- }
- }
- for(int i=1; i<=k; k++){
- for(int j=1; j<=k-1; j++){
- if(d[cit[j+1]]<d[cit[j]]) swap(cit[j], cit[j+1]);
- }
- }
- for(int i=1; i<=k; i++){
- cout << i << " " << cit[i] << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement