Advertisement
MAGCARI

Taep Nitrous

Aug 10th, 2022 (edited)
553
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. /*
  2.     Task    : Taep Nitrous
  3.     Author  : Phumipat C. [MAGCARI]
  4.     Language: C++
  5.     Created : 09 August 2022 [18:48]
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. struct A{
  10.     int v,w,k;
  11.     bool operator < (const A&o) const{
  12.         return w>o.w;
  13.     }
  14. };
  15. priority_queue<A > heap;
  16. vector<A > g[5010];
  17. int dis[5010][110];
  18. int main(){
  19.     int n,m,k,u,v,w;
  20.     scanf("%d %d %d",&n,&m,&k);
  21.     while(m--){
  22.         scanf("%d %d %d",&u,&v,&w);
  23.         g[u].push_back({v,w,0});
  24.         g[v].push_back({u,w,0});
  25.     }
  26.     for(int i=1;i<=n;i++)
  27.         for(int j=0;j<=k;j++)
  28.             dis[i][j] = 1e9;
  29.    
  30.     dis[1][0] = 0;
  31.     heap.push({1,0,0});
  32.     while(!heap.empty()){
  33.         A now = heap.top();
  34.         heap.pop();
  35.         for(auto x:g[now.v]){
  36.             //no nitrous
  37.             if(dis[now.v][now.k] + x.w < dis[x.v][now.k]){
  38.                 dis[x.v][now.k] = dis[now.v][now.k] + x.w;
  39.                 heap.push({x.v,dis[x.v][now.k],now.k});
  40.             }
  41.             //use nitrous
  42.             if(dis[now.v][now.k] + x.w/2 < dis[x.v][now.k+1]){
  43.                 dis[x.v][now.k+1] = dis[now.v][now.k] + x.w/2;
  44.                 heap.push({x.v,dis[x.v][now.k+1],now.k+1});
  45.             }
  46.         }
  47.     }
  48.     int ans = 1e9;
  49.     for(int i=0;i<=k;i++)
  50.         ans = min(ans,dis[n][i]);
  51.     printf("%d\n%d\n%d\n",dis[n][0],ans,dis[n][0] - ans);
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement