2263 Heavy Cargo

PKU

http://poj.org/problem?id=2263

概要

出発点から目的地までのパスの中で、パスの最小容量の辺の容量が最大になるようなパスを見つける問題。
ただ少し入力が面倒。

ソース

#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int cap[200][200];
int n;

int main() {
  int scenum = 1,r,i,j,k,a;
  string s,t;
  while(cin>>n>>r, n|r) {
    map<string,int> idx;
    memset(cap, 0, sizeof(cap));

    rep(i,r) {
      cin>>s>>t>>a;
      if(idx.find(s) == idx.end()) idx[s] = idx.size()-1;
      if(idx.find(t) == idx.end()) idx[t] = idx.size()-1;
      cap[idx[s]][idx[t]] = cap[idx[t]][idx[s]] = a;
    }

    rep(k,n) rep(i,n) rep(j,n)
      cap[i][j] = max(cap[i][j], min(cap[i][k], cap[k][j]));

    cin>>s>>t;
    cout<<"Scenario #"<<scenum<<endl;
    cout<<cap[idx[s]][idx[t]]<<" tons"<<endl;
    cout<<endl;
    scenum++;
  }
}