SHARE
TWEET

codeforce - Dijkstra?

jakaria_hossain Jun 3rd, 2019 (edited) 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. const int MAX=1e5+10;
  6. int dist[MAX],par[MAX];
  7. #define ii pair<int,int>
  8. vector< ii > adjlist[MAX];
  9. bitset<MAX>visited;
  10.  
  11.  
  12. bool Dijstra(int start, int endd)
  13. {
  14.     fill(dist,dist+endd+2,INFINITY);
  15.     priority_queue<ii,vector<ii>,greater<ii> >pq;
  16.     pq.push(ii(0,start));
  17.     dist[start]=0;
  18.     par[start]=-1;
  19.     while(!pq.empty())
  20.     {
  21.         int u= pq.top().second;
  22.         pq.pop();
  23.         if(u==endd)return true;
  24.  
  25.         visited[u]=true;
  26.         for(auto &pr : adjlist[u])
  27.         {
  28.             int v=pr.first;
  29.             int weight=pr.second;
  30.  
  31.             if(!visited[v] && dist[u]+weight<dist[v])
  32.             {
  33.                 dist[v]=dist[u]+weight;
  34.                 pq.push(ii(dist[v],v));
  35.                 par[v]=u;
  36.  
  37.             }
  38.         }
  39.     }
  40.     return false;
  41. }
  42.  
  43. int main()
  44. {
  45.     int edge;
  46.  
  47.     scanf("%d %d",&n,&edge);
  48.     while(edge--)
  49.     {
  50.         int u,v,weight;
  51.         scanf("%d %d %d",&u,&v,&weight);
  52.         adjlist[u].push_back(ii(v,weight));
  53.         adjlist[v].push_back(ii(u,weight));
  54.     }
  55.     if(Dijstra(1,n))
  56.     {
  57.         vector<int>path;
  58.         for(edge=n;edge!=-1;edge=par[edge])path.push_back(edge);
  59.         for(int i=path.size()-1;i>0;i--)cout<<path[i]<<" ";
  60.         printf("%d\n",path[0]);
  61.     }
  62.     else printf("-1\n");
  63.     return 0;
  64. }
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