10099 The Tourist Guide

/*
La solución se basa en la relajación max min para el maximum bottleneck problem
Se asume como elemento neutro de max a 0 y al elemento neutro de min como inf para
que son un bellman ford se resuelva esto en O(VE)
*/


#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int N,R;
  int test=1;
 
  while(cin>>N>>R && N){
   vector<pair<int,int> > edg(R);//aristas
   vector<int> cap(R);//capacidades
  
   for(int i=0;i<R;i++){
    cin>>edg[i].first>>edg[i].second;
    cin>>cap[i];
    edg[i].first--;
    edg[i].second--;
   }
   int s,d,p;
   cin>>s>>d>>p;
   s--;d--;
   #define inf 1000000
   vector<int> sol(N,0);
   sol[s]=inf;
  
   for(int i=0;i<N-1;i++){
    //las aristas son bidireccionales
    for(int j=0;j<R;j++){
     int u=edg[j].first;
     int v=edg[j].second;
     int w=cap[j];
     int a=min(sol[u],w);
     int b=min(sol[v],w);
     if(b>sol[u]) sol[u]=b;
     if(a>sol[v]) sol[v]=a;
    }
   }
  
   cout<<"Scenario #"<<test++<<endl;
   int cant=sol[d]-1;//podemos llevar una persona menos que sol[d], ya que debemos viajar en el carro
   cout<<"Minimum Number of Trips = "<<(p+cant-1)/cant<<endl<<endl;
  }
}