Advertisement
YEZAELP

o58_oct_c2_routesontrees

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