fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define inf 1000000
  4. using namespace std;
  5. typedef pair<int,int> ii;
  6. int p,target;
  7. vector<ii> adjls[10005];
  8. vector<ii> adjlt[10005];
  9. vector<int> dist[2];
  10. int dijkstra(int s,int x)
  11. {
  12.  
  13.     vector<ii> *adjl;
  14.     if(x == 0)
  15.         adjl=adjls;
  16.     else
  17.         adjl=adjlt;
  18.  
  19.     dist[x][s] = 0;
  20.     int maxtoll=-1;
  21.     priority_queue<ii> pq;
  22.     pq.push({0,s});
  23.     while(!pq.empty())
  24.     {
  25.         int u=pq.top().second,d=pq.top().first; pq.pop();
  26.         if(d>dist[x][u]) continue;
  27.         for(int j=0;j<adjl[u].size();++j)
  28.         {
  29.             int v=adjl[u][j].first,w=adjl[u][j].second;
  30.             if(x == 1)
  31.                 if(dist[0][v]+w+d<=p && w>maxtoll)
  32.                     maxtoll = w;
  33.             if((dist[x][u]+w) < dist[x][v] )
  34.             {
  35.  
  36.  
  37.                 dist[x][v] = dist[x][u]+w;
  38.                 pq.push({dist[x][v],v});
  39.             }
  40.         }
  41.     }
  42.     return maxtoll;
  43. }
  44. int main()
  45. {
  46.     int t;
  47.     scanf("%d",&t);
  48.     while(t--){
  49.     int n,m,s; scanf("%d%d%d%d%d",&n,&m,&s,&target,&p);
  50.     for(int i=0;i<=n;++i){
  51.         adjls[i].clear();
  52.         adjls[i].reserve(100005);
  53.         adjlt[i].clear();
  54.         adjlt[i].reserve(100005);
  55.         }
  56.     dist[0].assign(n+2,1000000);
  57.     dist[1].assign(n+2,1000000);
  58.     while(m--)
  59.     {
  60.         int u,v,c;
  61.         scanf("%d%d%d",&u,&v,&c);
  62.         adjls[u].push_back({v,c});
  63.         adjlt[v].push_back({u,c});
  64.  
  65.     }
  66.     dijkstra(s,0);
  67.     printf("%d\n",dijkstra(target,1));
  68.  
  69.  
  70.  
  71.     }
  72.  
  73. }
  74.  
Success #stdin #stdout 0s 3668KB
comments (?)
stdin
copy 
2
5 6 1 5 10
1 2 7
2 5 4
1 3 6
3 5 3
1 4 5
4 5 4
2 1 1 2 10
1 2 20
stdout
copy 
6
-1
https://ideone.com/RoxYGd
language:
C++14 (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!