fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, a, b;
  5. vector<pair<int, int> > ke[400009];
  6. int d[400009][11];
  7. bool marked[400009][11];
  8.  
  9. struct info {
  10.     int d;
  11.     int u;
  12.     int w;
  13.     info(int _d, int _u, int _w) : d(_d), u(_u), w(_w) {}
  14.  
  15.     bool operator()(const info x) {
  16.         if (d < x.d) return true;
  17.     }
  18. };
  19.  
  20. struct infoComparator {
  21.     bool operator()(const info& t1, const info& t2) {
  22.         return t1.d > t2.d;
  23.     }
  24. };
  25.  
  26. main() {
  27.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28.     cin >> n >> m;
  29.     for (int i = 1; i <= m; i++) {
  30.         int u, v, w;
  31.         cin >> u >> v >> w;
  32.         // cout << u << " " << v << " " << w << endl;
  33.         ke[u].push_back({v + n, w});
  34.         ke[v].push_back({u + n, w});
  35.         ke[v + n].push_back({u, w});
  36.         ke[u + n].push_back({v, w});
  37.         d[u][w] = d[v][w] = d[v + n][w] = d[u + n][w] = INT_MAX;
  38.     }
  39.  
  40.     priority_queue<info, vector<info>, infoComparator> pq;
  41.  
  42.     pq.push({0, 1, 0});
  43.     int ans = INT_MAX;
  44.  
  45.     while (pq.size()) {
  46.         auto top = pq.top();
  47.         pq.pop();
  48.  
  49.         int u = top.u, w = top.w;
  50.  
  51.         if (marked[u][w]) continue;
  52.  
  53.         if (u == n) {
  54.             ans = top.d;
  55.             break;
  56.         }
  57.  
  58.         marked[u][w] = true;
  59.  
  60.         for (auto& [v, _w] : ke[u]) {  // c(u,v) = w
  61.             if (marked[v][_w]) continue;
  62.  
  63.             if (u <= n) {
  64.                 if (d[v][_w] >= top.d) {
  65.                     d[v][_w] = top.d;
  66.                     pq.push({top.d, v, _w});
  67.                 }
  68.             } else {
  69.                 int cost = top.d + w * _w;
  70.                 if (cost < d[v][_w]) {
  71.                     d[v][_w] = cost;
  72.                     pq.push({cost, v, _w});
  73.                 }
  74.             }
  75.         }
  76.     }
  77.  
  78.     cout << (ans < INT_MAX ? ans : -1) << endl;
  79. }
Success #stdin #stdout 0.01s 13924KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/c4Gihj
language:
C++14 (gcc 8.3)
created:
1 day 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!