SHARE
TWEET

Untitled

a guest Apr 26th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. using namespace std;
  5. main(){
  6.     int n,m,s,j,i,k,e,inf=2009000999;deque<int>q;
  7.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8.     cin>>n>>m>>s; vector<pair<int,int> >a[n];
  9.     vector<int>d(n,inf); vector<bool>f(n,true);
  10.     for(;m;--m){ cin>>i>>j>>k;
  11.         a[i].push_back({j,k}); a[j].push_back({i,k});}
  12.     d[s]=0;q.push_back(s);f[i]=false;
  13.     while(!q.empty()){ i=q.front();q.pop_front();f[i]=true;
  14.         for(auto c:a[i]){ j=c.first;e=c.second;
  15.             if(d[j]>d[i]+e){
  16.                 if(d[j]==inf){q.push_back(j);f[j]=false;}
  17.                 else if (f[j]){q.push_front(j);f[j]=false;}
  18.                 d[j]=d[i]+e;}}}
  19.         for(auto b:d)cout<<b<<' ';}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top