UVa 10099 - The Tourist Guide

// UVa 10099 - The Tourist Guide
#include <queue>
#include <iostream>
#include <string.h>

using namespace std;

struct Edge {
	int a;
	int b;
	int c;
};

bool operator<(Edge x, Edge y) {
	return x.c < y.c;
}

int main() {

	int n, r;
	int cas = 0;

	cin >> n >> r;

	while (n != 0 || r != 0) {
		cas++;

		int e[101][101];
		memset(e, 0, sizeof(e));

		for (int j = 0; j < r; j++) {
			int c1, c2, p;
			cin >> c1 >> c2 >> p;
			p--;
			e[c1][c2] = p;
			e[c2][c1] = p;
		}
		int s, d, t;
		cin >> s >> d >> t;

		priority_queue<Edge> q;
		int T[101];
		memset(T, 0, sizeof(T));
		bool yet[101];
		memset(yet, true, sizeof(yet));

		T[s] = t;
		yet[s] = false;
		for (int i = 1; i <= n; i++)
			if (e[s][i] > 0) {
				Edge edge = { s, i, e[s][i] };
				q.push(edge);
			}

		while (!q.empty()) {
			Edge edge = q.top();
			q.pop();
			T[edge.b] = max(T[edge.b], min(T[edge.a], edge.c));
			if (yet[edge.b]) {
				for (int i = 1; i <= n; i++)
					if (e[edge.b][i] > 0 && yet[i]) {
						Edge ed = { edge.b, i, e[edge.b][i] };
						q.push(ed);
					}
				yet[edge.b] = false;
			}
		}
		int sol = t / T[d];
		if (t % T[d] > 0)
			sol++;

		cout << "Scenario #" << cas << endl;
		cout << "Minimum Number of Trips = " << sol << endl;
		cout << endl;

		cin >> n >> r;
	}

	return 0;
}