YEZAELP

TOI15: Cave

Oct 25th, 2021
625
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. using pi = pair <int, int>;
  5. using pii = pair <int, pi>;
  6. const int INF = 2e9;
  7. const int N = 2e3 + 10;
  8. const int T = 1e9;
  9. vector <pi> g[N], node, cdis;
  10. int dis[N][N];
  11. bool vs[N][N];
  12. int n, st, ed, m;
  13.  
  14. int main(){
  15.  
  16.     scanf("%d%d%d%d", &n, &st, &ed, &m);
  17.  
  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<n;j++){
  26.             dis[i][j] = INF;
  27.             vs[i][j] = false;
  28.         }
  29.     }
  30.  
  31.     /// dis[v][count edge]
  32.     priority_queue <pii, vector<pii>, greater<pii>> pq;
  33.     dis[st][0] = 0;
  34.     pq.push({dis[st][0], {st, 0}});
  35.     while(!pq.empty()){
  36.         int d = pq.top().first;
  37.         int u = pq.top().second.first;
  38.         int e = pq.top().second.second;
  39.         pq.pop();
  40.         if(vs[u][e]) continue;
  41.         vs[u][e] = true;
  42.         if(e + 1 == n) continue;
  43.         for(auto vw: g[u]){
  44.             int v = vw.first;
  45.             int w = vw.second;
  46.             if(!vs[v][e + 1] and d + w < dis[v][e + 1]){
  47.                 dis[v][e + 1] = d + w;
  48.                 pq.push({dis[v][e + 1], {v, e + 1}});
  49.             }
  50.         }
  51.     }
  52.  
  53.     /// cdis[u] = {dis, e};
  54.     int bf = INF;
  55.     for(int e=1;e<=n-1;e++){
  56.         if(dis[ed][e] <= T and dis[ed][e] < bf){
  57.             cdis.push_back({dis[ed][e], e});
  58.             bf = dis[ed][e];
  59.         }
  60.     }
  61.  
  62.     int L;
  63.     scanf("%d", &L);
  64.  
  65.     for(int i=0;i<L;i++){
  66.         int h;
  67.         scanf("%d", &h);
  68.         int mn = INF;
  69.         for(auto we: cdis){
  70.             int w = we.first;
  71.             int e = we.second;
  72.             mn = min(mn, w + (e - 1) * h);
  73.         }
  74.         printf("%d ", mn);
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
  80. /*
  81.     state graph: dis(u, จำนวน edge) = ระยะทางที่น้อยที่สุดจาก st ไป u ใด ๆ
  82.     Query: dis(ed, จำนวน edge) + (จำนวน edge - 1) * hi
  83. */
RAW Paste Data