Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<queue>
- #include<vector>
- using namespace std;
- main(){
- int n,m,s,j,i,k,e,inf=2009000999;deque<int>q;
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- cin>>n>>m>>s; vector<pair<int,int> >a[n];
- vector<int>d(n,inf); vector<bool>f(n,true);
- for(;m;--m){ cin>>i>>j>>k;
- a[i].push_back({j,k}); a[j].push_back({i,k});}
- d[s]=0;q.push_back(s);f[i]=false;
- while(!q.empty()){ i=q.front();q.pop_front();f[i]=true;
- for(auto c:a[i]){ j=c.first;e=c.second;
- if(d[j]>d[i]+e){
- if(d[j]==inf){q.push_back(j);f[j]=false;}
- else if (f[j]){q.push_front(j);f[j]=false;}
- d[j]=d[i]+e;}}}
- for(auto b:d)cout<<b<<' ';}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement