fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fi first
  5. #define se second
  6. typedef pair<ll, ll> pii;
  7. typedef pair<pii, pii> rect;
  8.  
  9. const int MAXN = 2e5+5, LOG = 19;
  10. const int MOD = 998244353;
  11.  
  12. ll N, M, K, T, P, Q, A, B, C, D, ans;
  13. ll d[MAXN];
  14. vector<pii> adj[MAXN];
  15. vector <int> ins[MAXN], era[MAXN];
  16.  
  17. int main () {
  18.     cin >> N >> M >> K >> T >> P >> Q;
  19.     ans=C=D=1e18;
  20. // express
  21.     for(int i=1; i<=M; i++){
  22.       cin >> A >> B >> C >> D;
  23.       adj[A].push_back({B, D});
  24.       adj[B].push_back({A, D});
  25.       ins[A].push_back(C);
  26.       era[B].push_back(C);
  27.     }
  28. // komuter
  29.    multiset <ll> ms;  
  30.     for (int i =1; i < N; i++){
  31.         for (auto c : ins[i]) ms.insert(c);
  32.         for (auto c : era[i]) ms.erase(ms.find(c));
  33.         //insert erase
  34.         if(ms.empty()) continue;
  35.         adj[i].push_back({i+1, *ms.begin()});
  36.         adj[i+1].push_back({i, *ms.begin()});
  37.     }
  38.     // biaya keluar masuk
  39.     for(int i=1; i<=N; i++){
  40.       adj[i+N].push_back({i, T});
  41.       adj[i].push_back({i+N, 0});
  42.     }
  43.     for(int i=1; i<N; i++){
  44.       adj[i+N].push_back({i+N+1, K});
  45.       adj[i+N+1].push_back({i+N, K});
  46.     }
  47.  
  48.     for(int i=1; i<=N*2; i++){
  49.       d[i] = 1e18;
  50.     }
  51.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  52.     pq.push({0, P+N});
  53.     d[P+N] = 0;
  54.     while(!pq.empty()){
  55.       auto[dist, cur] = pq.top();
  56.       pq.pop();
  57.       if(cur==Q or cur == N+Q){
  58.         ans = min(ans, dist);
  59.   cout << ans << "\n";
  60.         return  0;
  61.       }
  62. if (d[cur] != dist) continue;
  63.       for(auto[nx, w] : adj[cur]){
  64.         if (w+dist < d[nx]) {
  65.           d[nx] = w+dist;
  66.           pq.push({w+dist, nx});
  67.         }
  68.       }
  69.     }
  70.     cout << ans << "\n";
  71. }
  72.  
  73.  
Success #stdin #stdout 0.01s 18608KB
comments (?)
stdin
copy 
10 2 10 1 9 5
7 10 10 8
1 6 8 1
stdout
copy 
38
https://ideone.com/fVD4su
language:
C++ (gcc 8.3)
created:
8 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!