fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int MAX = 2e6 + 5;
  5. const int MOD = 1e9 + 7;
  6. int n, m, u1, u2, v;
  7. int dist1[MAX], dist2[MAX], dist3[MAX];
  8. int dx[] = {-1, 0, 1, 0};
  9. int dy[] = {0, 1, 0, -1};
  10. pair<int, int> start, fin;
  11. vector<pair<int, int>> g[MAX], rev_g[MAX];
  12. void DIJKSTRA(int start, int dist[], vector<pair<int, int>> g[MAX]) {
  13.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  14.     for(int i = 1; i <= n; i++) dist[i] = 2e18;
  15.     dist[start] = 0;
  16.     q.push({dist[start], start});
  17.     while(!q.empty()) {
  18.         int cost = q.top().first;
  19.         int u = q.top().second;
  20.         q.pop();
  21.         if(cost != dist[u]) continue;
  22.         for(auto e : g[u]) {
  23.             int v = e.first;
  24.             int w = e.second;
  25.             if(dist[v] > dist[u] + w) {
  26.                 dist[v] = dist[u] + w;
  27.                 q.push({dist[v], v});
  28.             }
  29.         }
  30.     }
  31. }
  32. signed main()
  33. {
  34.     ios_base::sync_with_stdio(0);
  35.     cin.tie(0); cout.tie(0);
  36.     if(fopen("gay.inp", "r")) {
  37.         freopen("gay.inp", "r", stdin);
  38.         freopen("gay.out", "w", stdout);
  39.     }
  40.     cin >> n >> m >> u1 >> u2 >> v;
  41.     for(int i = 1; i <= m; i++) {
  42.         int u, v, w;
  43.         cin >> u >> v >> w;
  44.         g[u].push_back({v, w});
  45.         rev_g[v].push_back({u, w});
  46.     }
  47.     DIJKSTRA(u1, dist1, g);
  48.     DIJKSTRA(u2, dist2, g);
  49.     DIJKSTRA(v, dist3, rev_g);
  50.     int ans = 2e18;
  51.     for(int i = 1; i <= n; i++) 
  52.         if(dist1[i] != 2e18  && dist2[i] != 2e18 && dist3[i] != 2e18)
  53.             ans = min(ans, dist1[i] + dist2[i] + dist3[i]);
  54.     if(ans == 2e18) cout << -1;
  55.     else cout << ans;
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.02s 102544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/CgAgDT
language:
C++14 (gcc 8.3)
created:
2 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!