fork download
copy 
  1. /*
  2. written by: Deinier Morales
  3. language: c++
  4. country: Cuba
  5. */
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <set>
  12. using namespace std;
  13. #define REP(i,n) for(int i=0;i<(int)n;++i)
  14. #define FOR(i,c) for( __typeof ((c).begin()) i = (c).begin() ; i != (c).end() ; ++i)
  15. #define ALL(c) (c).begin(),(c).end()
  16. #define INF 1000000000
  17.  
  18. typedef long long Weight;
  19. struct Edge
  20. {
  21.   public:
  22.     int src, dst;
  23.     Weight weight;
  24.     Edge()
  25.      {src=0;dst=0;weight=0;}
  26.     Edge(int psrc, int pdst, Weight pweight)
  27.      {src=psrc;dst=pdst;weight=pweight;}
  28. };
  29. bool operator < (const Edge &f,const Edge &g)
  30. {
  31.   return f.weight != g.weight ? f.weight > g.weight : f.src != g.src ? f.src < g.src : f.dst < g.dst;
  32. }
  33. typedef vector<Edge> Edges;
  34. typedef vector<Edges> Graph;
  35.  
  36. int c,n,a,x1,y,z,ini,fin;
  37. vector<Weight> dist;
  38. vector<int> prev;
  39. vector<int> cam;
  40. vector<int>::iterator iter;
  41. priority_queue<Edge> Q;
  42. Edges x;
  43. vector<Edge>::iterator iter1;
  44.  
  45. int main()
  46. {
  47.   scanf("%d",&c);
  48.   while(c--)
  49.    {
  50.      scanf("%d%d%d%d",&n,&a,&ini,&fin);
  51.      Graph g(n+1);
  52.      REP(i,a)
  53.       {
  54.         scanf("%d%d%d",&x1,&y,&z);
  55.         g[x1].push_back(Edge(x1,y,z));
  56.         g[y].push_back(Edge(y,x1,z));
  57.       }
  58.      dist.assign(n+1,INF);
  59.      dist[ini] = 0;
  60.      prev.assign(n+1,-1);
  61.  
  62.      for(Q.push(Edge(-2,ini,0));!Q.empty();)
  63.       {
  64.         Edge e = Q.top();
  65.         Q.pop();
  66.         if(prev[e.dst] != -1)
  67.           continue ;
  68.         prev[e.dst] = e.src;
  69.         x = g[e.dst];
  70.         iter1 = x.begin();
  71.         while(iter1!=x.end())
  72.          {
  73.            if(dist[iter1->dst] > e.weight+iter1->weight)
  74.             {
  75.               dist[iter1->dst] = e.weight + iter1->weight;
  76.               Q.push(Edge(iter1->src, iter1->dst, e.weight + iter1->weight));
  77.             }
  78.            iter1++;
  79.          }
  80.       }
  81.  
  82.      if(dist[fin] == INF)
  83.        printf("NONE\n");
  84.      else
  85.        printf("%ld\n",dist[fin]);
  86.    }
  87.   return 0;
  88. }
Success #stdin #stdout 0.01s 2868KB
comments (?)
stdin
copy 
2
4 2 1 4
1 2 5
3 4 5
4 4 1 4
1 2 5
2 3 5
3 4 5
4 2 6
stdout
copy 
NONE
11
https://ideone.com/HiwivK
language:
C++ (gcc 8.3)
created:
12 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!