jakaria_hossain

SPOJ - Easy dijkstar problem

Jun 4th, 2019
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast()(ios_base::sync_with_stdio(false),cin.tie(NULL));
  4. int const M= 1e9+1;
  5. int const N= 1e4+1;
  6. bool vis[N];
  7. int cost[N];
  8.  
  9. vector<vector<pair<int,int> > > root;
  10.  
  11.  
  12. void dijkstra(int src)
  13. {
  14. int v,c;
  15. priority_queue<pair<int,int> >q;
  16. cost[src]=0;
  17. q.push(make_pair(0,src));
  18. while(!q.empty())
  19. {
  20. v=q.top().second;
  21. c=-q.top().first;
  22. q.pop();
  23. if(vis[v])continue;
  24. vis[v]=true;
  25. for(auto pr: root[v])
  26. {
  27. if(pr.second+c<cost[pr.first])
  28. {
  29. cost[pr.first]=pr.second+c;
  30. q.push(make_pair(-(pr.second+c),pr.first));
  31. }
  32. }
  33. }
  34. }
  35. int main()
  36. {
  37. int t;
  38. scanf("%d",&t);
  39. while(t--)
  40. {
  41. int node, edge;
  42. scanf("%d %d",&node,&edge);
  43. root.clear();
  44. root.resize(node);
  45. int u,v,w;
  46. for(int i=0;i<=node;i++)cost[i]=M;
  47. memset(vis,false,sizeof(vis));
  48.  
  49. for(int i=0;i<edge;i++)
  50. {
  51.  
  52. scanf("%d %d %d",&u,&v,&w);
  53. u--,v--;
  54. root[u].push_back(make_pair(v,w));
  55. }
  56.  
  57. scanf("%d %d",&u,&v);
  58. u--,v--;
  59. dijkstra(u);
  60. if(cost[v]==M)printf("NO\n");
  61. else printf("%d\n",cost[v]);
  62. }
  63. }
RAW Paste Data