YEZAELP

TOI12: Cable Car

Jul 11th, 2020
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF=1e9;
  4. using pi=pair<int,int>;
  5. vector <pi> g[2501];
  6. int n,m;
  7. int main(){
  8.     int mx_w=-INF;
  9.     scanf("%d%d",&n,&m);
  10.     vector <int> dis(n+1,-INF);
  11.     vector <bool> visited(n+1,false);
  12.     for(int i=1;i<=m;i++){
  13.         int u,v,w;
  14.         scanf("%d%d%d",&u,&v,&w);
  15.         g[u].push_back({v,w});
  16.         g[v].push_back({u,w});
  17.         mx_w=max(mx_w,w);
  18.     }
  19.     int s,t,p,weight=0;
  20.     scanf("%d%d%d",&s,&t,&p);
  21.  
  22.     priority_queue<pi> pq;
  23.     dis[s]=mx_w;
  24.     pq.push({dis[s],s});
  25.     while(pq.size()>0){
  26.         int u,d;
  27.         d=pq.top().first;
  28.         u=pq.top().second;
  29.         pq.pop();
  30.  
  31.         if(visited[u])
  32.             continue;
  33.         visited[u]=true;
  34.         if(u==t){
  35.             weight=d;
  36.             break;
  37.         }
  38.         for(auto vw:g[u]){
  39.             int v,w;
  40.             v=vw.first;
  41.             w=vw.second;
  42.             if(!visited[v] and min(w,d)>dis[v]){
  43.                 pq.push({ min(d,w),v });
  44.             }
  45.         }
  46.     }
  47.  
  48.     if( p%(weight-1) > 0 ) printf("%d", ( p / (weight-1) )+1 );
  49.     else printf("%d",p/(weight-1));
  50.  
  51.     return 0;
  52. }
RAW Paste Data Copied