fork download
copy 
  1. // ~~ icebear love attttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebearat"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 2e5 + 5;
  38. int n, m;
  39. vector<ii> G[N];
  40. ll dist[N][2][2];
  41.  
  42. void init(void) {
  43.     cin >> n >> m;
  44.     FOR(i, 1, m) {
  45.         int u, v, w;
  46.         cin >> u >> v >> w;
  47.         G[u].pb(mp(v, w));
  48.         G[v].pb(mp(u, w));
  49.     }
  50. }
  51.  
  52. struct state {
  53.     int node, s1, s2;
  54.     ll dist;
  55.     bool operator > (const state &other) const {
  56.         return dist > other.dist;
  57.     }
  58. };
  59.  
  60. void process(void) {
  61.     priority_queue<state, vector<state>, greater<state>> Q;
  62.     memset(dist, 0x3f, sizeof dist);
  63.     Q.push({1, 0, 0, 0});
  64.     dist[1][0][0] = 0;
  65.     while(!Q.empty()) {
  66.         auto T = Q.top(); Q.pop();
  67.         if (dist[T.node][T.s1][T.s2] != T.dist) continue;
  68.         for(ii x : G[T.node]) {
  69.             int v, w; tie(v, w) = x;
  70.             if (minimize(dist[v][T.s1][T.s2], T.dist + w))
  71.                 Q.push({v, T.s1, T.s2, dist[v][T.s1][T.s2]});
  72.             if (T.s1 == false) {
  73.                 if (minimize(dist[v][true][T.s2], T.dist))
  74.                     Q.push({v, true, T.s2, dist[v][true][T.s2]});
  75.             }
  76.             if (T.s2 == false) {
  77.                 if (minimize(dist[v][T.s1][true], T.dist + 2 * w))
  78.                     Q.push({v, T.s1, true, dist[v][T.s1][true]});
  79.             }
  80.             if (T.s1 == false && T.s2 == false) {
  81.                 if (minimize(dist[v][true][true], T.dist + w))
  82.                     Q.push({v, true, true, dist[v][true][true]});
  83.             }
  84.         }
  85.     }
  86.  
  87.     FOR(i, 2, n) cout << dist[i][1][1] << ' ';
  88. }
  89.  
  90. int main() {
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0); cout.tie(0);
  93.     if (fopen(task".inp", "r")) {
  94.         freopen(task".inp", "r", stdin);
  95.         freopen(task".out", "w", stdout);
  96.     }
  97.     int tc = 1;
  98. //    cin >> tc;
  99.     while(tc--) {
  100.         init();
  101.         process();
  102.     }
  103.     return 0;
  104. }
  105.  
  106.  
Success #stdin #stdout 0.01s 14500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vd272G
language:
C++14 (gcc 8.3)
created:
4 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!