YEZAELP

TOI14: Logistics

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