fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define ii pair < int , int >
  4. #define fi first
  5. #define se second
  6.  
  7. using namespace std;
  8.  
  9. const int N = 105;
  10.  
  11. int A, B, n, m;
  12. int dist[N];
  13.  
  14. vector < ii > a[2][105];
  15.  
  16. struct item
  17. {
  18.     int u, cost;
  19.     bool ok;
  20.     item(int _u = 0, int _cost = 0, bool _ok = 0){
  21.         u = _u;
  22.         cost = _cost;
  23.         ok = _ok;
  24.     }
  25. };
  26.  
  27. struct cmp
  28. {
  29.     bool operator()(item a, item b)
  30.     {
  31.         return a.cost < a.cost;
  32.     }
  33. };
  34.  
  35. priority_queue < item, vector < item >, cmp > q;
  36.  
  37.  
  38. void inp()
  39. {
  40.     cin >> A >> B;
  41.     cin >> n >> m;
  42.     for(int i = 1; i <= m; i++){
  43.         int u, v, w;
  44.         cin >> u >> v >> w;
  45.         a[1][u].push_back({v, w});
  46.         a[0][v].push_back({u, w});
  47.     }
  48. }
  49.  
  50.  
  51. int xuly(int x, int w)
  52. {
  53.     int tmp = x / 12;
  54.     x = x - tmp * 12;
  55.     if(x + w == 12){
  56.         return 1;
  57.     }
  58.     if(x + w < 12){
  59.         return 2;
  60.     }
  61.     return 0;
  62. }
  63.  
  64.  
  65.  
  66. void dijk()
  67. {
  68.     for(int i = 1; i <= n; i++){
  69.         dist[i] = 1e18;
  70.     }
  71.     dist[A] = 0;
  72.     q.push(item(A, 0, 1));
  73.     while(!q.empty())
  74.     {
  75.         int u = q.top().u;
  76.         int cost = q.top().cost;
  77.         int day = q.top().ok;
  78.         q.pop();
  79.         if(cost > dist[u]) continue;
  80.         for(int i = 0; i < a[day][u].size(); i++){
  81.             int v = a[day][u][i].fi;
  82.             int w = a[day][u][i].se;
  83.             if(dist[v] > dist[u] + w && xuly(dist[u], w) > 0){
  84.                 if(xuly(dist[u], w) == 1){
  85.                     dist[v] = dist[u] + w;
  86.                     q.push(item(v, dist[v], (day + 1) % 2));
  87.                 }
  88.                 else{
  89.                     dist[v] = dist[u] + w;
  90.                     q.push(item(v, dist[v], day));
  91.                 }
  92.             }
  93.             else if(xuly(dist[u], w) == 0){
  94.                 int tmp = dist[u] / 12;
  95.                 int x = tmp * 12 + 12 + 12;
  96.                 q.push(item(v, min(dist[v], x + w), day));
  97.             }
  98.             if(xuly(dist[u], w) > 0){
  99. //                cout <<  "CCCCCCCCCCCC" << v << "CCCCCCCCC" << '\n';
  100.                 int tmp = dist[u] / 12;
  101.                 int x = tmp * 12 + 12;
  102.                 q.push(item(v, x, (day + 1) % 2));
  103.             }
  104.         }
  105.     }
  106. }
  107.  
  108.  
  109.  
  110. main()
  111. {
  112.     ios_base::sync_with_stdio(0);
  113.     cin.tie(0); cout.tie(0);
  114.     inp();
  115.     dijk();
  116.     for(int i = 1; i <= n; i++){
  117.         cout << "node" << i << " " << dist[i] << '\n';
  118.     }
  119. }
  120.  
Success #stdin #stdout 0.01s 5248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SdlbSU
language:
C++ (gcc 8.3)
created:
10 days 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!