jakaria_hossain

codeforce - Dijkstra?

Jun 3rd, 2019
92
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