fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FORE(i,a,b) for(int i = a; i <= b; ++i)
  4. #define FORD(i,a,b) for(int i = a; i >= b; --i)
  5. #define FOR(i,a,b) for(int i = a; i < b; ++i)
  6. #define pb push_back
  7. #define endl '\n'
  8. #define ll long long
  9. #define X first
  10. #define Y second
  11.  
  12. const int MAXN = 1e5 * 5;
  13. const int base = 1e9 + 7;
  14. const int N = 5000;
  15. typedef pair<ll,ll> ii;
  16. typedef pair<ii,int> iii;
  17.  
  18. int n,m;
  19. int p[MAXN];
  20. ll d[MAXN],f[MAXN];
  21. priority_queue<iii> h;
  22. vector<int> a[MAXN],c[MAXN];
  23.  
  24. void dijkstra()
  25. {
  26.     FORE(i,1,n) d[i] = 1e15;
  27.     FORE(i,1,n) f[i] = 0;
  28.     d[1] = 0;
  29.     f[1] = p[1];
  30.     h.push(iii(ii(0,p[1]),1));
  31.     while(h.size())
  32.     {
  33.         int u = h.top().Y;
  34.         ll du = -h.top().X.X;
  35.         ll fu = h.top().X.Y;
  36.         h.pop();
  37.         if (du != d[u] || f[u] != fu) continue;
  38.         for(int i = 0; int v = a[u][i]; ++i)
  39.         if (d[v] > d[u] + c[u][i])
  40.         {
  41.             d[v] = d[u] + c[u][i];
  42.             f[v] = f[u] + p[v];
  43.             h.push(iii(ii(-d[v],f[v]),v));
  44.         }
  45.         else
  46.         if (d[v] == d[u] + c[u][i] && f[v] < f[u] + p[v])
  47.         {
  48.             f[v] = f[u] + p[v];
  49.             h.push(iii(ii(-d[v],f[v]),v));
  50.         }
  51.     }
  52. }
  53.  
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0); cin.tie(0);
  57.     //freopen("vo17phd.inp" , "r" , stdin);
  58.     //("vo17phd.out" , "w" , stdout);
  59.     cin>>n;
  60.     FORE(i,1,n) cin>>p[i];
  61.     cin>>m;
  62.     FORE(i,1,m)
  63.     {
  64.         int u,v,w;
  65.         cin>>u>>v>>w;
  66.         a[u].pb(v); c[u].pb(w);
  67.         a[v].pb(u); c[v].pb(w);
  68.     }
  69.     FORE(i,1,n) a[i].pb(0);
  70.     dijkstra();
  71.     if (d[n] == 1e15) cout<<"impossible"<<endl;
  72.     else cout<<d[n]<<' '<<f[n]<<endl;
  73.     return 0;
  74. }
Runtime error #stdin #stdout 0s 24952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PyoEoD
language:
C++14 (gcc 8.3)
created:
7 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!