UVa 10986 - Sending email

// UVa 10986 - Sending email
// Dijkstra

#include <iostream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;

#define MaxN 20000
#define integer unsigned long long int

struct edge {
	int b;integer c;
};

struct dsol {
	bool reachable;integer cost;
};

bool operator <(edge x, edge y) {
	return x.c > y.c || (x.c == y.c && x.b > y.b);
}

int n, s, t;
vector<edge> lnk[MaxN];

dsol dijkstra() {
	priority_queue<edge> q;
	integer dist[MaxN];
	memset(dist, 127, sizeof(dist));
	bool yet[MaxN];
	memset(yet, true, sizeof(yet));
	integer oo = dist[0];
	int i = s;
	dist[s] = 0;
	while (i != -1 && i != t) {
		yet[i] = false;
		for (int j = 0; j < lnk[i].size(); j++) {
			int b = lnk[i][j].b;
			integer c = lnk[i][j].c;
			if (yet[b] && (dist[b] == oo || dist[i] + c < dist[b])) {
				dist[b] = dist[i] + c;
				q.push( { b, dist[b] });
			}
		}
		while (!q.empty() && !yet[q.top().b])
			q.pop();
		i = (q.empty() ? -1 : q.top().b);
	}
	return {dist[t] != oo, dist[t]};
}

int main() {
	int ttt;
	cin >> ttt;
	for (int tt = 1; tt <= ttt; tt++) {
		int m;
		cin >> n >> m >> s >> t;
		for (int i = 0; i < n; i++)
			lnk[i].clear();
		for (int j = 0; j < m; j++) {
			int a, b;
			integer c;
			cin >> a >> b >> c;
			lnk[a].push_back( { b, c });
			lnk[b].push_back( { a, c });
		}
		dsol sol = dijkstra();
		if (!sol.reachable)
			printf("Case #%d: unreachable\n", tt);
		else {
			printf("Case #%d: ", tt);
			cout << sol.cost << endl;
		}
	}
	return 0;
}