SHARE
TWEET

SPOJ - Easy dijkstar problem

jakaria_hossain Jun 4th, 2019 50 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
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top