fork download
copy 
  1. // https://o...content-available-to-author-only...i.info/problem/lhphcm_bus
  2. #include <bits/stdc++.h>
  3. #define pii pair<int, int>
  4. #define ll long long
  5. #define fi first
  6. #define se second
  7. using namespace std;
  8.  
  9. const int maxn = 2e5+3;
  10.  
  11. int n, m, s, t, news, newt;
  12. ll dist3[maxn][3], dist1[maxn], dist2[maxn];
  13. vector<pii> graph[maxn];
  14.  
  15. void dijkstra(int src, ll dist[]) {
  16.     for (int i = 1; i <= n; i++) dist[i] = LLONG_MAX;
  17.     bitset<maxn> visited = 0;
  18.     priority_queue<pii> pq; pq.push({0, src});
  19.     dist[src] = 0;
  20.     while (!pq.empty()) {
  21.         int u = pq.top().second; pq.pop();
  22.         if (visited[u]) continue;
  23.         visited[u] = true;
  24.         for (int i = 0, v, w; i < graph[u].size(); i++) {
  25.             v = graph[u][i].first, w = graph[u][i].second; if (v == u) continue;
  26.             if (dist[v] <= dist[u] + w) continue;
  27.             dist[v] = dist[u] + w;
  28.             pq.push({-dist[v], v});
  29.         }
  30.     }
  31. }
  32.  
  33. struct Edge {
  34.     int v; ll w; int state;
  35.     Edge (int V, ll W, int S = 0) {v = V; w = W; state = S;}
  36.     bool operator < (const Edge &b) {return w < b.w || (w == b.w && state < b.state);}
  37. };
  38. struct comp {
  39.     bool operator () (const Edge &a, const Edge &b)
  40.         {return a.w > b.w || (a.w == b.w && a.state > b.state);}
  41. };
  42.  
  43.  
  44. void dijkstra2() {
  45.     for (int i = 1; i <= n; i++) dist3[i][0] = dist3[i][1] = dist3[i][2] = LLONG_MAX;
  46.     priority_queue<Edge, vector<Edge>, comp> pq; pq.push(Edge(news, 0, 0));
  47.     dist3[news][1] = dist3[news][2] = 0;
  48.     while (!pq.empty()) {
  49.         int u = pq.top().v, state = pq.top().state;
  50.         ll w = pq.top().w; pq.pop();
  51.         if (dist3[u][state] <= w) continue;
  52.         dist3[u][state] = w;
  53.         if (u == newt) return;
  54.         for (int i = 0, v, ww; i < graph[u].size(); i++) {
  55.             v = graph[u][i].fi, ww = graph[u][i].se; if (v == u) continue;
  56.             if (state <= 1 && min(dist1[u]+dist2[v], dist2[u]+dist1[v])+ww == dist1[t]) // on a shortest path
  57.                 {if (dist3[v][1] > w) pq.push(Edge(v, w, 1));}
  58.             else if (dist3[v][(state>=1)<<1] > w+ww)
  59.                 pq.push(Edge(v, w+ww, (state>=1)<<1));
  60.         }
  61.     }
  62. }
  63.  
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(0);
  68.     cin >> n >> m >> s >> t >> news >> newt;
  69.     int a, b, c;
  70.     while (m--) {
  71.         cin >> a >> b >> c;
  72.         graph[a].push_back({b, c});
  73.         graph[b].push_back({a, c});
  74.     }
  75.     dijkstra(s, dist1); dijkstra(t, dist2);
  76. //    for (int i = 1; i <= n; i++) cout << dist1[i] << ' '; cout << '\n';
  77. //    for (int i = 1; i <= n; i++) cout << dist2[i] << ' '; cout << '\n';
  78.     dijkstra2();
  79.     cout << min(dist3[newt][0], min(dist3[newt][1], dist3[newt][2]))  << '\n';
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 12584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/RoXnfh
language:
C++14 (gcc 8.3)
created:
7 hours 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!