TOI12: Cable Car

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pi=pair<int,int>;
vector <pi> g[2501];
int n,m;
int main(){
    int mx_w=-INF;
    scanf("%d%d",&n,&m);
    vector <int> dis(n+1,-INF);
    vector <bool> visited(n+1,false);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        mx_w=max(mx_w,w);
    }
    int s,t,p,weight=0;
    scanf("%d%d%d",&s,&t,&p);

    priority_queue<pi> pq;
    dis[s]=mx_w;
    pq.push({dis[s],s});
    while(pq.size()>0){
        int u,d;
        d=pq.top().first;
        u=pq.top().second;
        pq.pop();

        if(visited[u])
            continue;
        visited[u]=true;
        if(u==t){
            weight=d;
            break;
        }
        for(auto vw:g[u]){
            int v,w;
            v=vw.first;
            w=vw.second;
            if(!visited[v] and min(w,d)>dis[v]){
                pq.push({ min(d,w),v });
            }
        }
    }

    if( p%(weight-1) > 0 ) printf("%d", ( p / (weight-1) )+1 );
    else printf("%d",p/(weight-1));

    return 0;
}