Advertisement
YEZAELP

o57_oct_c2_kshort

Jan 14th, 2022
1,080
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 1e18;
  6. const int maxN = 1e4 + 10;
  7. const int maxS = 50 + 10;
  8. using pl = pair <lli, lli>;
  9. using pll = pair <lli, pl>;
  10. vector <pl> ng[maxN], sg[maxN];
  11. bool vs[maxN][maxS];
  12. lli dis[maxN][maxS];
  13. lli N, M, S, L;
  14.  
  15. int main(){
  16.  
  17.     scanf("%lld %lld %lld %lld", &N, &M, &S, &L);
  18.  
  19.     for(int i=1;i<=M;i++){
  20.         lli u, v, w;
  21.         scanf("%lld %lld %lld", &u, &v, &w);
  22.         ng[u].push_back({v, w});
  23.     }
  24.  
  25.     for(int i=1;i<=S;i++){
  26.         lli u, v, w;
  27.         scanf("%lld %lld %lld", &u, &v, &w);
  28.         sg[u].push_back({v, w});
  29.     }
  30.  
  31.     priority_queue <pll, vector <pll>, greater <pll>> pq;
  32.     dis[1][0] = 0;
  33.     pq.push({ dis[1][0] , {1, 0} });
  34.  
  35.     for(int u=0;u<=N;u++){
  36.         for(int l=0;l<=L;l++){
  37.             dis[u][l] = INF;
  38.         }
  39.     }
  40.  
  41.     while(!pq.empty()){
  42.         lli d = pq.top().first;
  43.         lli u = pq.top().second.first;
  44.         lli l = pq.top().second.second;
  45.         pq.pop();
  46.         if(vs[u][l]) continue;
  47.         vs[u][l] = true;
  48.         if(u == N){
  49.             printf("%lld", d);
  50.             return 0;
  51.         }
  52.         for(auto vw: ng[u]){
  53.             lli v = vw.first;
  54.             lli w = vw.second;
  55.             if(!vs[v][l] and d + w < dis[v][l]){
  56.                 dis[v][l] = d + w;
  57.                 pq.push({dis[v][l], {v, l}});
  58.             }
  59.         }
  60.         if(l < S){
  61.             for(auto vw: sg[u]){
  62.                 lli v = vw.first;
  63.                 lli w = vw.second;
  64.                 if(!vs[v][l + 1] and d + w < dis[v][l + 1]){
  65.                     dis[v][l + 1] = d + w;
  66.                     pq.push({dis[v][l + 1], {v, l + 1}});
  67.                 }
  68.             }
  69.         }
  70.     }
  71.  
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement