fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=a;i<=b;i++)
  3. #define ll long long
  4. #define For(i,a,b) for(int i=a;i <b;i++)
  5. #define vi vector<int>
  6. #define ii pair<int,int>
  7. #define lii pair<long long,int>
  8. #define vii vector<ii>
  9. #define vlii vector<lii>
  10. #define pb push_back
  11. #define mp make_pair
  12. #define fi first
  13. #define se second
  14.  
  15. using namespace std;
  16. const int maxn=50001;
  17. const int maxm=500000;
  18.  
  19. struct re
  20. {
  21.     int x,y,w;
  22. };
  23. int n,m;
  24. ll d[maxn],res=1e12,dn[maxn];
  25. bool ok;
  26. vii a[maxn],ra[maxn];
  27. bool vis[maxn];
  28. re e[maxm];
  29.  
  30. void enter()
  31. {
  32.     freopen("SHORTEST.INP","r",stdin);
  33.     cin >> n >> m;
  34.     rep(i,1,m)
  35.     {
  36.         int x,y,w; cin >> x >> y >> w;
  37.         e[i].x=x; e[i].y=y; e[i].w=w;
  38.         a[x].pb(mp(y,w));
  39.         ra[y].pb(mp(x,w));
  40.     }
  41. }
  42.  
  43. void dijkstra()
  44. {
  45.     priority_queue<lii,vlii,greater<lii> > heap;
  46.     heap.push(mp(0,1));
  47.     rep(i,1,n)
  48.     {
  49.         d[i]=1e12;
  50.         dn[i]=1e12;
  51.     }
  52.     d[1]=0; dn[n]=0;
  53.     while (!heap.empty())
  54.     {
  55.         int u=heap.top().se;
  56.         heap.pop();
  57.         if (vis[u]) continue;
  58.         vis[u]=1;
  59.         For(i,0,a[u].size())
  60.         {
  61.             int v=a[u][i].fi;
  62.             int w=a[u][i].se;
  63.             if (d[v]>d[u]+w)
  64.             {
  65.                 d[v]=d[u]+w;
  66.                 heap.push(mp(d[v],v));
  67.             }
  68.         }
  69.     }
  70.     rep(i,1,n) vis[i]=0;
  71.     while (!heap.empty()) heap.pop();
  72.     heap.push(mp(0,n));
  73.     while (!heap.empty())
  74.     {
  75.         int u=heap.top().se;
  76.         heap.pop();
  77.         if (vis[u]) continue;
  78.         vis[u]=1;
  79.         For(i,0,ra[u].size())
  80.         {
  81.             int v=ra[u][i].fi;
  82.             int w=ra[u][i].se;
  83.             if (dn[v]>dn[u]+w)
  84.             {
  85.                 dn[v]=dn[u]+w;
  86.                 heap.push(mp(dn[v],v));
  87.             }
  88.         }
  89.     }
  90. }
  91. void process()
  92. {
  93.     dijkstra();
  94.     rep(i,1,m)
  95.     {
  96.         int x,y,w;
  97.         x=e[i].x; y=e[i].y; w=e[i].w;
  98.         if (d[x]+dn[y]+w>d[n]) res=min(res,d[x]+dn[y]+w);
  99.     }
  100. }
  101.  
  102. void out()
  103. {
  104.     freopen("SHORTEST.OUT","w",stdout);
  105.     if (res==1e12) res=-1;
  106.     cout << res;
  107. }
  108. int main()
  109. {
  110.     ios_base::sync_with_stdio(0);
  111.     enter();
  112.     process();
  113.     out();
  114. }
  115.  
Runtime error #stdin #stdout #stderr 0s 11320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/L2tt7n
language:
C++ (gcc 8.3)
created:
10 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!