fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //variable
  4. #define ld long double
  5. #define ll long long
  6. #define db double
  7. #define ii pair<int,int>
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. //vector
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define len(a) (int)a.length()
  16. #define sz(a) (int)a.size()
  17. //mask
  18. #define BIT(i) (1LL<<(i))
  19. //better code, debugger
  20. #define watch(n) cerr << #n << ": " << n << endl
  21. #define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
  22. #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
  23. #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
  24. #define fIlE "test."
  25. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  26. //mt19937 RAND(seed);
  27. const int mod = 1e9 + 7;
  28. inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
  29. inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
  30. inline int mul(int u,int v){return (ll)u*v%mod;}
  31. #define tt pair<ll, int>
  32. const ll inf = 1e16;
  33. int n, m;
  34. vector<ii> a[100000 + 100];
  35. vector<ii> g[100000 + 100];
  36. ll dist1[100000 + 100];
  37. ll distn[100000 + 100];
  38. void solve()
  39. {
  40.     cin >> n >> m;
  41.     while(m--){
  42.         int u, v, d;
  43.         cin >> u >> v >> d;
  44.         a[u].pb(mp(v, d));
  45.         g[v].pb(mp(u, d));
  46.     }
  47.     priority_queue<tt, vector<tt>, greater<tt> > haha;
  48.     forw(i, 1, n)
  49.         dist1[i] = inf;
  50.     haha.push(mp(dist1[1] = 0, 1));
  51.     while(!haha.empty())
  52.     {
  53.         int u; ll d;
  54.         u = haha.top().s, d = haha.top().f;
  55.         haha.pop();
  56.         if (dist1[u] < d) continue;
  57.         for (auto [v, e] : a[u])
  58.         {
  59.             if (dist1[v] > e + d)
  60.             {
  61.                 dist1[v] = e + d;
  62.                 haha.push(mp(dist1[v], v));
  63.             }
  64.         }
  65.     }
  66.     priority_queue<tt, vector<tt>, greater<tt> > haha2;
  67.     forw(i, 1, n)
  68.         distn[i] = inf;
  69.     haha2.push(mp(distn[n] = 0, n));
  70.     while(!haha2.empty())
  71.     {
  72.         int u; ll d;
  73.         u = haha2.top().s, d = haha2.top().f;
  74.         haha2.pop();
  75.         if (distn[u] < d) continue;
  76.         for (auto [v, e] : g[u])
  77.         {
  78.             if (distn[v] > e + d)
  79.             {
  80.                 distn[v] = e + d;
  81.                 haha2.push(mp(distn[v], v));
  82.             }
  83.         }
  84.     }
  85.     ll ans = inf;
  86.     forw(u, 1, n) for (auto [v, e] : a[u])
  87.         ans = min(ans, dist1[u] + distn[v] + e / 2);
  88.     cout << ans;
  89.  
  90. }
  91. signed main()
  92. {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(0);
  95.     if (fopen(fIlE"inp", "r"))
  96.         freopen(fIlE"inp","r",stdin);
  97.     if (fopen(fIlE"out", "r"))
  98.         freopen(fIlE"out","w",stdout);
  99.     //time_t TIME_TU=clock();
  100.     int t=1;
  101. //    cin>>t;
  102.     while(t--)
  103.         solve();
  104.     //time_t TIME_TV=clock();
  105.     //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 8244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000000000000
https://ideone.com/xhHhsw
language:
C++ (gcc 8.3)
created:
12 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!