fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
  3. #define rep(i,n) REP(i,0,n)
  4. using namespace std;
  5.  
  6. struct G{
  7.     struct E{ int t, c; };
  8.     int n;
  9.     vector<vector<E>> g;
  10.     G(int n) : n(n), g(n){}
  11.     void add_undirected_edge(int s, int t, int c){
  12.         g[s].emplace_back(E{t, c});
  13.         g[t].emplace_back(E{s, c});
  14.     }
  15.     // undirected なのだけ. (そうでなくしたければ, 逆グラフを作る)
  16.     int dijk(int s, int t){
  17.         vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(2);
  18.         vector<vector<int>> d(2, vector<int>(n, numeric_limits<int>::max() / 2));
  19.         pq[0].emplace(d[0][s] = 0, s);
  20.         pq[1].emplace(d[1][t] = 0, t);
  21.         vector<int> fin(n);
  22.         for(bool cont = true; cont and !pq[0].empty() and !pq[1].empty(); ){
  23.             for(int i = 0; i < 2; ++i){
  24.                 if(pq[i].empty()) continue;
  25.                 int u, c; tie(c, u) = pq[i].top(); pq[i].pop();
  26.                 if(c > d[i][u]) continue;
  27.                 if(++fin[u] == 2){
  28.                     cont = false;
  29.                     break;
  30.                 }
  31.                 for(auto &e : g[u]) if(d[i][e.t] > c + e.c)
  32.                     pq[i].emplace(d[i][e.t] = c + e.c, e.t);
  33.             }
  34.         }
  35.         int res = numeric_limits<int>::max();
  36.         for(int u = 0; u < n; ++u) res = min(res, d[0][u] + d[1][u]);
  37.         return res;
  38.     }
  39. };
  40.  
  41. bool solve(){
  42.     int n, m; cin >> n >> m;
  43.     G g(n);
  44.     rep(_, m){
  45.         int u, v, c; cin >> u >> v >> c;
  46.         g.add_undirected_edge(--u, --v, c);
  47.     }
  48.     cout << g.dijk(0, n-1) << endl;
  49.     return true;
  50. }
  51. signed main(){
  52.     cin.tie(nullptr);
  53.     ios_base::sync_with_stdio(false);
  54.     cout << std::fixed << std::setprecision(10);
  55.     solve();
  56.     return 0;
  57. }
  58. // vim:set foldmethod=marker commentstring=//%s:
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
stdout
copy 
90
https://ideone.com/UayEyc
language:
C++14 (gcc 8.3)
created:
8 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!