fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct edge
  4. {
  5.     int ind, cost;
  6.     bool operator <(const edge & x) const   //for priority queue.....
  7.     {
  8.         return (cost >= x.cost);
  9.     }
  10. };
  11. int i , j , k , n , m , a, b, c, d;
  12. vector<edge> g[10100];
  13. int visited[10100];
  14. int dist[10100];
  15. priority_queue<edge> pq;
  16. void djkstra(int s)
  17. {
  18.     memset(dist, -1, sizeof(dist));
  19.     memset(visited, 0, sizeof(visited));
  20.     edge start;
  21.     start.ind = s;
  22.     start.cost = 0;
  23.     pq.push(start);
  24.     vector<edge>::iterator it;
  25.     dist[s] = 0;
  26.     while(!pq.empty())
  27.     {
  28.         edge x = pq.top();
  29.         pq.pop();
  30.         if( visited[x.ind] == 1)
  31.             continue;
  32.         visited[x.ind] = 1;
  33.         for( it = g[x.ind].begin(); it != g[x.ind].end(); it++)
  34.         {
  35.             if( dist[it->ind] < 0 || dist[it->ind] > dist[x.ind] + it->cost )
  36.             {
  37.                 dist[it->ind] = dist[x.ind] + it->cost;
  38.                 pq.push(*it);
  39.             }
  40.         }
  41.     }
  42. }
  43. int main()
  44. {
  45.     int tc;
  46.     scanf("%d", &tc);
  47.     while(tc--)
  48.     {
  49.         scanf("%d %d", &n, &m);
  50.         for( i = 0 ; i <= n ; i++)
  51.         {
  52.             g[i].clear();
  53.         }
  54.         for( i = 0 ; i < m ; i++)
  55.         {
  56.             scanf("%d%d%d", &a, &b, &c);
  57.             edge e1, e2;
  58.             e1.ind = a;
  59.             e2.ind = b;
  60.             e1.cost = e2.cost = c;
  61.             g[a].push_back(e2);
  62.         }
  63.         scanf("%d%d",&a,&b);
  64.         djkstra(a);
  65.         if( dist[b] == -1)
  66.             printf("NO\n");
  67.         else
  68.             printf("%d\n", dist[b]);
  69.     }
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 3676KB
comments (?)
stdin 
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
stdout 
12
5
NO
https://ideone.com/9JiIMw
language:
C++ (gcc 8.3)
created:
10 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!