abinash_hstu

Dijkstra using pair

Jan 16th, 2016
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #include<utility>
  8. using namespace std;
  9.  
  10. #define mx 100002
  11. #define  w first
  12. #define  u second
  13. #define  pb push_back
  14. #define  mp make_pair
  15.  
  16. typedef  pair <int, int> pii;
  17.  
  18. vector<int>graph[mx],cost[mx];
  19. long long dist[mx];
  20. int parent[mx];
  21.  
  22. void dijkstra(int n)
  23. {
  24.     for(int i=0;i<=n;i++)
  25.         parent[i]=dist[i]=-1;
  26.     priority_queue<pii,vector<pii > ,greater<pii > >Q;
  27.     Q.push(mp(0,1));
  28.     dist[1]=0;
  29.     while(!Q.empty())
  30.     {
  31.         pii top=Q.top();
  32.         Q.pop();
  33.         int u=top.u;
  34.         for(int i=0; i<(int)graph[u].size(); i++)
  35.         {
  36.             int v=graph[u][i];
  37.             if(dist[u]+cost[u][i]<dist[v]||dist[v]==-1)
  38.             {
  39.                 dist[v]=dist[u]+cost[u][i];
  40.                 parent[v]=u;
  41.                 Q.push(mp(dist[v],v));
  42.             }
  43.         }
  44.     }
  45. }
  46. int main()
  47. {
  48.     int n,e;
  49.     scanf("%d%d",&n,&e);
  50.  
  51.     for(int i=0; i<e; i++)
  52.     {
  53.         int u,v,w;
  54.         scanf("%d %d %d",&u,&v,&w);
  55.         graph[u].push_back(v);
  56.         graph[v].push_back(u);
  57.         cost[u].push_back(w);
  58.         cost[v].push_back(w);
  59.  
  60.     }
  61.     dijkstra(n);
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment