fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef int64_t   ll;
  7. typedef pair<int,int> ii;
  8.  
  9. #define EL printf("\n")
  10. #define pb push_back
  11. #define mp make_pair
  12. #define X  first
  13. #define Y  second
  14.  
  15. struct data {
  16.     int u, d;
  17.     data (int u, int d) {
  18.         this->u = u;
  19.         this->d = d;
  20.     }
  21.     bool operator < (const data &other) const {
  22.         return (d > other.d);
  23.     }
  24. };
  25.  
  26. const int   N = 150, M = N*N, oo = 10000000;
  27. int         n, m, k, u, v, c, s, t, d[N], dd[N], res[N], trace[N];
  28. vector<ii>  a[N];
  29. priority_queue<data> heap;
  30.  
  31. void reset()
  32. {
  33.     res[0] = 0;
  34.     for (int i=1;i<=n;i++)
  35.         d[i] = oo, dd[i] = 0, trace[i] = -1;
  36.     d[s] = 0;
  37.     for (int i=1;i<=n;i++) heap.push(data(i,d[i]));
  38. }
  39.  
  40. void dijkstra()
  41. {
  42.     for (;;) {
  43.         data top = heap.top();
  44.         heap.pop();
  45.         if (d[top.u] != top.d) continue;
  46.         int u = top.u;
  47.         dd[u] = 1;
  48.         if (u == t) break;
  49.         for (int i=0;i<a[u].size();i++) {
  50.             int v = a[u][i].X;
  51.             if (!dd[v] and d[v] > d[u] + a[u][i].Y) {
  52.                 d[v] = d[u] + a[u][i].Y;
  53.                 trace[v] = u;
  54.                 heap.push(data(v,d[v]));
  55.             }
  56.         }
  57.     }
  58.  
  59. }
  60.  
  61. int main()
  62. {
  63.     //freopen("INP.INP","r",stdin);
  64.     //freopen("OUT.OUT","w",stdout);
  65.  
  66.     scanf("%d%d%d", &n,&m,&k);
  67.     for (int i=1;i<=m;i++) {
  68.         scanf("%d%d%d", &u,&v,&c);
  69.         a[u].pb(mp(v,c));
  70.         a[v].pb(mp(u,c));
  71.     }
  72.     while (k--) {
  73.         scanf("%d%d%d", &c, &s, &t);
  74.         reset();
  75.         dijkstra();
  76.         if (c == 0) printf("%d\n", d[t]);
  77.         else {
  78.             while (t != -1) {
  79.                 res[++res[0]] = t;
  80.                 t = trace[t];
  81.             }
  82.             printf("%d ", res[0]);
  83.             for (int i=res[0];i>0;i--) printf("%d ", res[i]);
  84.             EL;
  85.         }
  86.     }
  87.  
  88.     return 0;
  89. }
  90.  
  91.  
Success #stdin #stdout 0s 2872KB
comments (?)
stdin
copy 
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3
stdout
copy 
3
3 1 2 3
https://ideone.com/b02Hrk
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!