fork 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 ke {
  16.     int v, c;
  17.     ll  w;
  18.     ke(int v, int c, ll w) {
  19.         this->v = v;
  20.         this->c = c;
  21.         this->w = w;
  22.     }
  23. };
  24.  
  25. struct data {
  26.     int u, c;
  27.     ll  d;
  28.     data(int u, int c, ll d) {
  29.         this->u = u;
  30.         this->c = c;
  31.         this->d = d;
  32.     }
  33.     bool operator < (const data &other) const {
  34.         return d > other.d;
  35.     }
  36. };
  37.  
  38. const int   N = 150000;
  39. const ll    oo = 1e16;
  40. int         n, m, C, q, s, t, u, v, c;
  41. ll          w, d[N];
  42. vector<ke>  a[N];
  43. priority_queue<data> heap;
  44.  
  45. void dijkstra()
  46. {
  47.     for (int i=1;i<=n;i++) d[i] = oo;
  48.     d[s] = 0ll;
  49.     heap.push(data(s,-1,d[s]));
  50.     while (!heap.empty()) {
  51.         data top = heap.top();
  52.         heap.pop();
  53.         u = top.u;
  54.         if (d[u] != top.d) continue;
  55.         for (int i=0;i<a[u].size();i++) {
  56.             v = a[u][i].v;
  57.             c = a[u][i].c;
  58.             w = a[u][i].w;
  59.             if (c != top.c and d[v] > d[u] + w) {
  60.                 d[v] = d[u] + w;
  61.                 heap.push(data(v,c,d[v]));
  62.             }
  63.         }
  64.     }
  65.     for (int i=1;i<=n;i++) if (d[i] == oo) d[i] = -1;
  66. }
  67.  
  68. int main()
  69. {
  70.     //freopen("INP.INP","r",stdin);
  71.     //freopen("OUT.OUT","w",stdout);
  72.  
  73.     scanf("%d %d %d", &n, &m, &C);
  74.     while (m--) {
  75.         scanf("%d %d %I64d %d", &u, &v, &w, &c);
  76.         a[u].pb(ke(v,c,w));
  77.     }
  78.  
  79.     scanf("%d %d", &s, &q);
  80.  
  81.     dijkstra();
  82.  
  83.     while (q--) {
  84.         scanf("%d", &t);
  85.         printf("%I64d\n", d[t]);
  86.     }
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 6164KB
comments (?)
stdin
copy 
5 4 1000
1 2 10 1
2 3 10 2
3 4 10 2
4 5 10 1
1 5
1
2
3
4
5
stdout
copy 
                                                               0
                                                              10
                                                              20
                                                              -1
                                                              -1
https://ideone.com/2ZJt6L
language:
C++ (gcc 8.3)
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!