Advertisement
YEZAELP

SMMR-176: Trip Planner

Apr 19th, 2021 (edited)
174
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 N = 1e3;
  7. const int C = 1e2;
  8. const int INF = 2e9;
  9. vector <pi> g[N+10];
  10. int p[N+10];
  11. bool visited[N+10][C+10];
  12. int dis[N+10][C+10];
  13. int mn = INF;
  14.  
  15. int f(int c, int s, int e){
  16.  
  17.     if(c < mn) return -1;
  18.  
  19.     priority_queue <pii, vector <pii>, greater <pii>> pq;
  20.     dis[s][c] = 0;
  21.     pq.push({0, {s, 0}});
  22.  
  23.     while(!pq.empty()){
  24.         int d = pq.top().first;
  25.         int u = pq.top().second.first;
  26.         int oil = pq.top().second.second;
  27.         pq.pop();
  28.         if(visited[u][oil])
  29.             continue;
  30.         visited[u][oil] = true;
  31.         if(u == e){
  32.             return d;
  33.         }
  34.         for(auto vw: g[u]){
  35.             int v = vw.first;
  36.             int w = vw.second;
  37.             if(oil >= w and !visited[v][oil-w] and d < dis[v][oil-w]){
  38.                 dis[v][oil-w] = d;
  39.                 pq.push({dis[v][oil-w], {v, oil-w} });
  40.             }
  41.             if(oil + 1 <= c and oil + 1 >= w and !visited[v][oil+1-w] and d + p[u] < dis[v][oil+1-w]){
  42.                 dis[v][oil+1-w] = d + p[u];
  43.                 pq.push({dis[v][oil+1-w] , {v, oil+1-w}});
  44.             }
  45.         }
  46.         if(oil + 1 <= c) pq.push({d+p[u], {u, oil+1}});
  47.     }
  48.  
  49.     return -1;
  50. }
  51.  
  52. int main(){
  53.  
  54.     int n, m;
  55.     scanf("%d%d", &n, &m);
  56.  
  57.     for(int i=0;i<n;i++){
  58.          scanf("%d", &p[i]);
  59.     }
  60.  
  61.     for(int i=1;i<=m;i++){
  62.         int u, v, w;
  63.         scanf("%d%d%d", &u, &v, &w);
  64.         g[u].push_back({v, w});
  65.         g[v].push_back({u, w});
  66.         mn = min(mn, w);
  67.     }
  68.  
  69.     int q;
  70.     scanf("%d", &q);
  71.  
  72.     while(q--){
  73.         int c, s, e;
  74.         scanf("%d%d%d", &c, &s, &e);
  75.  
  76.         for(int i=0;i<=n;i++){
  77.             for(int j=0;j<=c;j++){
  78.                 visited[i][j] = false;
  79.                 dis[i][j] = INF;
  80.             }
  81.         }
  82.  
  83.         int ans = f(c, s, e);
  84.         if(ans == -1) printf("impossible");
  85.         else printf("%d", ans);
  86.         printf("\n");
  87.  
  88.     }
  89.  
  90.     return 0;
  91. }
  92. /*
  93. ไม่ควรเติมน้ำมันทุกแบบ
  94. ควร ค่อยๆเติมแล้วดูว่าเดินได้มั้ย  
  95. */
Advertisement
RAW Paste Data Copied
Advertisement