HDU-3631 Shortest Path 题解

题目大意

给你一张加权有向多重图，你可以对这张图进行两种操作

（1）在图中标记一个顶点。
（2）仅通过标记的顶点找到两个顶点之间的最短路径。

对于操作“ 0 x”，表示标记x点，如果点x已经被标记了，则输出“ ERROR! At point x“。

对于操作“ 1 x y”，如果未标记点x或点y，则输出“ERROR! At path x to y”；

如果无法通过标记顶点从x到达y，则输出“No such path”；

否则，输出最短路径的长度。

在两个连续的测试用例之间有一个空白行。

解题思路

看题意，很明显是多源最短路。

（但是我一开始没想到，直接用Dijkstra写了，然后TLE了。。

以标记点为中继点，不断更新最短距离，看是否能够只通过标记点到达。

不为INF就是可以到达。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int mark[330],vis[330],dis[330],n;
long long Map[330][330];

void floyd(int k) {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
		}
	}
}

void init() {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++)
			Map[i][j] = INF;
		Map[i][i] = 0;
	}
}

int main() {
	int  m, q,cnt = 1;
	while (cin >> n >> m >> q && n || m || q) {
		memset(mark, 0, sizeof(mark));
		init();
		if (cnt != 1)	cout << endl;//注意恶心人的输出格式
		cout << "Case " << cnt++ << ":" << endl;
		for (int i = 1; i <= m; i++) {
			int x, y;
			long long d;
			cin >> x >> y >> d;
			Map[x][y] = min(d,Map[x][y]);//多重图，注意找最小值
		}
		for (int i = 1; i <= q; i++) {
			int x;
			cin >> x ;
			if (x) {
				int node1, node2;
				cin >> node1 >> node2;
				if (!mark[node1] || !mark[node2]) 
					cout << "ERROR! At path " << node1 << " to " << node2 << endl;
				else {
					if (Map[node1][node2] >= INF)	cout << "No such path" << endl;
					else cout << Map[node1][node2] << endl;
				}
			}
			else {
				int node;
				cin >> node;
				if (mark[node])
					cout << "ERROR! At point " << node << endl;
				else {
					mark[node] = 1;
					floyd(node);
				}
			}
		}
	}
}