fork download
copy 
  1. ///Complexity: O(mlogm). n=number of edge,n=number of node.(analysis from shanto's book)
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define ll long long int
  7. #define pi pair<ll,ll>
  8. #define pii pair<pi,ll>
  9. struct node{
  10.     ll a,cost;
  11.     node(ll _a,ll _cost){
  12.         a=_a;
  13.         cost=_cost;
  14.     }
  15. };
  16.  
  17. bool operator<(node A, node B){
  18.     /// priority queue returns the greatest value.
  19.     /// So we need to write the comperator in a way.
  20.     /// So that cheapest value becomes greatest value.
  21.     return A.cost>B.cost;
  22. }
  23.  
  24. struct Edge{
  25.     ll v,w;
  26. };
  27.  
  28. vector<Edge> adj[1005];
  29. ll dist[1005];
  30. bool visit[1005];
  31. ll n;
  32.  
  33. ll dijkstra(ll s,ll destination){
  34.     priority_queue<node>PQ;
  35.     for(ll i=1;i<=n;i++){
  36.         dist[i]=1000000000;
  37.         visit[i]=0;
  38.     }
  39.     dist[s]=0;
  40.     PQ.push(node(s,0));
  41.     while(!PQ.empty()){
  42.         node u=PQ.top();
  43.         PQ.pop();
  44.  
  45.         if(visit[u.a]){ continue; } /// if(u.cost!=dist[u.a]){ continue; }
  46.         visit[u.a]=1;
  47.  
  48.         ///priority_queue তে edge এর weight অনুযায়ী sort হয় না। বরং, node এর cost অনুযায়ী sort হয়।
  49.         ///priority_queue এর সবচেয়ে ছোট cost এর node নিয়ে আগে কাজ করব। So, সেখান থেকে যেসব জায়গায় যাব, তাদের cost আমাদের current node এর cost এর থেকে বেশি/সমান হবে। So, priority_queue এর সবচেয়ে ছোট cost এর যে node টাকে নিয়ে একবার কাজ করে ফেলব, সেটাকে নিয়ে next time আর কাজ করা লাগবে না।
  50.  
  51.  
  52.         if(u.a==destination) return u.cost;
  53.         for(Edge e : adj[u.a]){
  54.             if(dist[e.v]>u.cost+e.w){
  55.                 dist[e.v]=u.cost +e.w;
  56.                 PQ.push(node(e.v,dist[e.v]));
  57.             }
  58.         }
  59.     }
  60.     return -1;
  61. }
  62.  
  63. int main()
  64. {
  65.     ll i,j,m,a,b,ans=0,k,c;
  66.  
  67.     cin>>n>>m;
  68.     Edge aa;
  69.  
  70.     for(i=0;i<m;i++){
  71.         cin>>a>>b>>c;
  72.         aa.v=b;
  73.         aa.w=c;
  74.         adj[a].push_back(aa);
  75.         aa.v=a;
  76.         adj[b].push_back(aa);
  77.     }
  78.     cin>>a>>b;
  79.     cout<<dijkstra(a,b)<<endl;
  80.  
  81. }
  82.  
Success #stdin #stdout 0s 4960KB
comments (?)
stdin
copy 
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
1 5
stdout
copy 
5
https://ideone.com/gOWQay
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!