fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ll long long
  5. #define N int(1e3)
  6. using namespace std;
  7. ll n, m;
  8. vector<pair<ll, ll>>adj[N+10];
  9. ll gt[N+10][N+10];
  10. pair<ll, ll>luu[N+10][N+10];
  11. ll a, b, k, g;
  12. ll g1[N+10], tg[N+10];
  13. bool vis[N+10];
  14. ll dis[N+10];
  15. void djs(ll s)
  16. {
  17.     for(int i = 1; i <= n; i++) dis[i] = 1e18;
  18.     priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
  19.     dis[s]=k+1;
  20.     pq.push({k,s});
  21.     while(!pq.empty())
  22.     {
  23.         auto top=pq.top();pq.pop();
  24.         ll u=top.se;
  25.         ll kc=top.fi;
  26.         if(kc>dis[u]) continue;
  27.         for(auto it:adj[u])
  28.         {
  29.             ll v=it.fi;
  30.             ll w=it.se;
  31.             ll them=0;
  32.             pair<ll,ll>ed=luu[u][v];
  33.             ll st=luu[u][v].fi;
  34.             ll en=luu[u][v].se;
  35.             if(dis[u]>=st && dis[u]<en) them=en-dis[u];
  36.  
  37.             if(dis[v] > dis[u] + w + them)
  38.             {
  39.                 dis[v] = dis[u] + w + them;
  40.                 pq.push({dis[v], v});
  41.             }
  42.         }
  43.     }
  44. }
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0);
  48.     cin.tie(0);
  49.     cout.tie(0);
  50.  
  51.     cin>>n>>m;
  52.     cin>>a>>b>>k>>g;
  53.     for(int i=1; i<=g; i++) cin>>g1[i];
  54.     for(int i=1; i<=m; i++)
  55.     {
  56.         ll u, v, w;
  57.         cin>>u>>v>>w;
  58.         adj[u].push_back({v, w});
  59.         adj[v].push_back({u, w});
  60.         gt[u][v]=w;
  61.         gt[v][u]=w;
  62.     }
  63.     tg[g1[1]]=1;
  64.     for(int i=1; i<g; i++)
  65.     {
  66.         ll u=g1[i];
  67.         ll v=g1[i+1];
  68.         ll cu=tg[u];
  69.         ll moi=tg[u]+gt[u][v];
  70.         luu[u][v]= {cu, moi};
  71.         luu[v][u]= {cu, moi};
  72.         tg[v]=moi;
  73.     }
  74.     memset(vis,0,sizeof vis);
  75.     djs(a);
  76.     cout<<dis[b]-(1+k);
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ann7Pb
language:
C++ (gcc 8.3)
created:
1 hour 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!