#include <iostream> #include <cstdio> #include <algorithm> #include <queue>//POJ2263 #include <map> #include <vector> #include <cstring> using namespace std; const int maxn = 210; const int maxm = 20000; int n; int r; int start, dest; //记录节点编号。 bool vis[maxn];//mark each point;//出队列后标记已经被更新过,如果在此访问不可更新其值则不再入队。 int value[maxn];//保存每个节点当前最大值,初始化为-1; //及时在更新 struct edge { int from; int to; int weight; }; struct point { int num; // 队列里面到节点编号。 int w; // 队列里面到,到达此节点到距离。 bool operator < (const point& b) const { return w < b.w; } }; vector<edge> G[maxn]; map<string, int> mymap; priority_queue<point> Q; int work() { edge tmp; point tmp_point; int Size = G[start].size(); for(int i = 0; i < Size; i++) { //初始化队列。 tmp = G[start][i]; tmp_point.num = tmp.to; tmp_point.w = tmp.weight; Q.push(tmp_point); value[tmp.to] = tmp.weight;//init value; // printf("value[%d] = %d ", tmp.to, tmp.weight); } while(!Q.empty()) { tmp_point = Q.top(); // printf("tmp_point.num = %d, tmp_point.w = %d ", tmp_point.num, tmp_point.w); Q.pop(); int len = G[tmp_point.num].size(); for(int i = 0; i < len; i++) { edge edge_tmp = G[tmp_point.num][i]; if(vis[edge_tmp.to]) { //已经被访问过,只是关心有可能得到解到,并入队。 if(value[edge_tmp.to] < min(edge_tmp.weight, tmp_point.w)) { value[edge_tmp.to] = min(edge_tmp.weight, tmp_point.w); point p; p.num = edge_tmp.to; p.w = value[edge_tmp.to]; Q.push(p); } } else {//未被访问过。 value[edge_tmp.to] = min(edge_tmp.weight, value[edge_tmp.from]); point p; p.num = edge_tmp.to; p.w = value[edge_tmp.to]; Q.push(p); } } vis[tmp_point.num] = true; if(tmp_point.num == dest) return tmp_point.w;//get result; } return value[n]; } void init() { while(!Q.empty()) Q.pop(); mymap.clear(); memset(vis, false, sizeof(vis)); for(int i = 0; i <= n; i++) { value[i] = -1; } } int main() { int counter = 1; while(scanf("%d%d", &n, &r)!=EOF) { init(); int cnt = 1; // 给节点编号。 if(n==0 && r==0) break; string tmp[2]; int weight; edge t; //临时变量 map<string, int>::iterator it; for(int i = 1; i <= r; i++) { cin >> tmp[0]; cin >> tmp[1]; for(int i = 0; i < 2; i++) { if(mymap.find(tmp[i])==mymap.end()) mymap[tmp[i]] = cnt++; } cin >> weight; t.from = mymap[tmp[0]]; t.to = mymap[tmp[1]]; t.weight = weight; G[t.from].push_back(t); t.from = mymap[tmp[1]]; t.to = mymap[tmp[0]]; G[t.from].push_back(t); } cin >> tmp[0] >> tmp[1]; start = mymap[tmp[0]], dest = mymap[tmp[1]]; int res = work(); printf("Scenario #%d ", counter++); printf("%d tons ", res); } return 0; }