10986 – Sending email

Given a network of servers and the connections between them with their latency, find the fastest path for sending a message.

A straight-forward path finding problem. Dijkstra will do and Bellman Ford will get TLE.

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;

vector<int> dijkstraD, dijkstraP;
void dijkstra(int s) {
	dijkstraD = vector<int>(graph.size(), numeric_limits<int>::max());
	dijkstraP = vector<int>(graph.size(), -1);
	priority_queue<pair<int, int> > q;
	dijkstraP[s] = -s - 1;
	dijkstraD[s] = 0;
	q.push(make_pair(dijkstraD[s], s));
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		if (dijkstraP[p.second] < 0) {
			dijkstraP[p.second] = -dijkstraP[p.second] - 1;
			for (map<int, int>::iterator itr = graph[p.second].begin();
				itr != graph[p.second].end(); ++itr)
				if (dijkstraP[itr->first] < 0
				&& dijkstraD[p.second] + graph[p.second][itr->first] < dijkstraD[itr->first]) {
					dijkstraP[itr->first] = -p.second - 1;
					dijkstraD[itr->first] = dijkstraD[p.second] + graph[p.second][itr->first];
					q.push(pair<int, int>(-dijkstraD[itr->first], itr->first));
				}
		}
	}
}

int main() {
	int N, n, m, s, t;
	cin >> N;
	for (int caseI = 0; caseI < N; ++caseI) {
		// input
		cin >> n >> m >> s >> t;
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, a, b, w; i < m; ++i)
			cin >> a >> b >> w, graph[a][b] = graph[b][a] = w;
		// solve
		dijkstra(s);
		cout << "Case #" << (caseI + 1) << ": ";
		if (dijkstraD[t] == numeric_limits<int>::max())
			cout << "unreachable";
		else
			cout << dijkstraD[t];
		cout << endl;
	}
	return 0;
}