fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define FIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  5.  
  6. #define ll long long
  7. #define endl '\n'
  8.  
  9. int DX[]= {0,0,1,-1};
  10. int DY[]= {1,-1,0,0};
  11. bool vis[105][105][2] {false};
  12.  
  13. const int N=1e5+10;
  14. int dis[N];
  15. vector<pair<int,int>>adj[N];
  16. void init()
  17. {
  18.     for(int i=0; i<N; i++)
  19.     {
  20.        dis[i]=1e9;
  21.     }
  22.  
  23.  
  24. }
  25.  
  26.  
  27. void Dijkstra(int src) // e log v
  28. {
  29.  
  30.     dis[src]=0;
  31.         //dis,node
  32.     priority_queue<pair<int,int>>Q;
  33.  
  34.     Q.push({-dis[src],src});
  35.  
  36.     while(Q.size())
  37.     {
  38.             // AUTO take best candidate
  39.         int u=Q.top().second;
  40.         int d=-Q.top().first;
  41.         Q.pop();
  42.       //  cout<<u<<endl;
  43.         if(d!=dis[u])
  44.         {
  45.             continue;
  46.         }
  47.          //   cout<<"pass  "<<u<<endl;
  48.         // relaxation
  49.  
  50.  
  51.         for( auto x: adj[u])
  52.         {
  53.           //  cout<<x.first<<" ";
  54.             int v=x.first;
  55.             int c=x.second;
  56.  
  57.             int newCost=d+c;
  58.            // cout<<newCost<<" "<<dis[v]<<endl;
  59.             if(newCost<dis[v])
  60.             {
  61.                 dis[v]=newCost;
  62.                 Q.push({-newCost,v});
  63.             }
  64.  
  65.         }
  66.        // cout<<endl;
  67.  
  68.     }
  69.  
  70.  
  71. }
  72.  
  73.  
  74.  
  75. int main()
  76. {
  77.  
  78.     int t;
  79.     cin>>t;
  80.     while(t--)
  81.     {
  82.         int n,m,src,dist;
  83.         cin>>n>>m>>src>>dist;
  84.         for(int i=0;i<m;i++)
  85.         {
  86.             int f,t,c;
  87.             cin>>f>>t>>c;
  88.             adj[f].push_back({t,c});
  89.             adj[t].push_back({f,c});
  90.         }
  91.         init();
  92.         Dijkstra(src);
  93.         if(dis[dist]==1e9)
  94.         {
  95.             cout<<"NONE"<<endl;
  96.         }
  97.         else
  98.         {
  99.             cout<<dis[dist]<<endl;
  100.         }
  101.     }
  102.  
  103. }
  104.  
Runtime error #stdin #stdout 0.01s 6036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iepGMP
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!