Advertisement
YEZAELP

o60_oct_c1_collecting

Apr 6th, 2021
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 50010;
  4. using pi = pair <int, int>;
  5. using pii = pair <int, pi>;
  6. const int INF = 2e9;
  7. vector <pi> g[N];
  8. int dis[N][40];
  9. bool visited[N][40];
  10. int level[N];
  11. int main(){
  12.  
  13.     for(int i=0;i<=50000;i++){
  14.         for(int j=0;j<=30;j++){
  15.             dis[i][j] = INF;
  16.             visited[i][j] = false;
  17.         }
  18.     }
  19.  
  20.     int n, m, L;
  21.     scanf("%d%d%d", &n, &m, &L);
  22.     int s, t;
  23.     scanf("%d%d", &s, &t);
  24.     for(int i=1;i<=n;i++){
  25.         scanf("%d", &level[i]);
  26.     }
  27.     for(int i=1;i<=m;i++){
  28.         int u, v, w;
  29.         scanf("%d%d%d", &u, &v, &w);
  30.         g[u].push_back({v, w});
  31.     }
  32.     priority_queue <pii, vector <pii>, greater <pii>> pq;
  33.     pq.push({0, {s, 0}});
  34.     while(!pq.empty()){
  35.         int d = pq.top().first;
  36.         int u = pq.top().second.first;
  37.         int l = pq.top().second.second;
  38.         pq.pop();
  39.         if(visited[u][l])
  40.             continue;
  41.         visited[u][l] = true;
  42.         if(l == L and u == t) {
  43.             printf("%d", d);
  44.             return 0;
  45.         }
  46.         for(auto vw: g[u]){
  47.             int v = vw.first;
  48.             int w = vw.second;
  49.             if(level[v] == l+1 and !visited[v][l+1] and d + w < dis[v][l+1]){
  50.                 dis[v][l+1] = d + w;
  51.                 pq.push({d+w, {v, l+1}});
  52.             }
  53.             else if(!visited[v][l] and d + w < dis[v][l]){
  54.                 dis[v][l] = d + w;
  55.                 pq.push({d+w, {v, l}});
  56.             }
  57.         }
  58.     }
  59.     printf("-1");
  60.     return 0;
  61. }
  62.  
Advertisement
RAW Paste Data Copied
Advertisement