PKU 2263 Heavy Cargo

• 最短経路の応用
• エッジを更新するときにそれまでの最大容量と道の容量の高い方を伝搬する
• 上はダイクストラ法、下はワーシャルフロイド法の解答

struct Dic {
	map<string, int> m;
	int get(const string& s) {
		map<string, int>::iterator it = m.find(s);
		if (it != m.end()) {
			return it->second;
		}
		const int index = m.size();
		m.insert(make_pair(s, index));
		return index;
	}
};

int main() {
	int scenarioIndex = 1;
	for (int n, r; cin >> n >> r && (n || r); ) {
		vector<vector<pair<int, int> > > g(n);
		Dic dic;
		for (int i = 0; i < r; ++i) {
			string from, to;
			int weight;
			cin >> from >> to >> weight;
			const int fromIndex = dic.get(from);
			const int toIndex = dic.get(to);
			g[fromIndex].push_back(make_pair(toIndex, weight));
			g[toIndex].push_back(make_pair(fromIndex, weight));
		}

		string start, goal;
		cin >> start >> goal;
		const int startIndex = dic.get(start);
		const int goalIndex = dic.get(goal);

		vector<int> dp(n);
		dp[startIndex] = INT_MAX;
		priority_queue<pair<int, int> > q;
		q.push(make_pair(INT_MAX, startIndex));
		while (!q.empty()) {
			const int currentCost = q.top().first;
			const int currentNode = q.top().second;
			q.pop();
			if (dp[currentNode] != currentCost) {
				continue;
			}

			for (vector<pair<int, int> >::iterator it = g[currentNode].begin(), itEnd = g[currentNode].end(); it != itEnd; ++it) {
				const int nextCost = min(currentCost, it->second);
				const int nextNode = it->first;
				if (dp[nextNode] < nextCost) {
					dp[nextNode] = nextCost;
					q.push(make_pair(nextCost, nextNode));
				}
			}
		}

		printf("Scenario #%d\n%d tons\n\n", scenarioIndex++, dp[goalIndex]);
	}
}

struct Dic {
	map<string, int> m;
	int get(const string& s) {
		map<string, int>::iterator it = m.find(s);
		if (it != m.end()) {
			return it->second;
		}
		const int index = m.size();
		m.insert(make_pair(s, index));
		return index;
	}
};

int main() {
	int scenarioIndex = 1;
	for (int n, r; cin >> n >> r && (n || r); ) {
		static int g[256][256];
		memset(g, 0, sizeof(g));
		Dic dic;
		for (int i = 0; i < r; ++i) {
			string from, to;
			int weight;
			cin >> from >> to >> weight;
			const int fromIndex = dic.get(from);
			const int toIndex = dic.get(to);
			g[fromIndex][toIndex] = max(g[fromIndex][toIndex], weight);
			g[toIndex][fromIndex] = max(g[toIndex][fromIndex], weight);
		}

		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					g[i][j] = max(g[i][j], min(g[i][k], g[k][j]));
				}
			}
		}

		string from, to;
		cin >> from >> to;
		const int fromIndex = dic.get(from);
		const int toIndex = dic.get(to);
		printf("Scenario #%d\n%d tons\n\n", scenarioIndex++, g[fromIndex][toIndex]);
	}
}