floyd插点。（看起来难实际很简单）
给你一个有向多重图（就是可能会有重边和自环，对应简单图），会标记一些点，然后再询问给定两点的最短路，要求该最短路上经过的点都是被标记过的（必然包括起点终点）。权值都为正，看样例，发现当起点终点相同时最短路必然是0（当然这个点得标记过才行）。其实这题就是把floyd的第一层循环k拆成在线处理了，给一个标记点，然后就运行一遍以这个标记点为k值的2/3版的floyd就完事了，当问最短路的时候都是建立在这句之前的操作上，那么就直接输出当前结果就ok了。
理解floyd的动态规划本质，所谓k就是个中介点，而且不用关心k的循环次序。每次输出的最短路绝对不会经过没标记的点，因为之前没拿那些点当中介点。
这道题输出也给你玩个文字游戏，要求每相邻两个case之间才能有空行，最后不能有。
#include#include #include #include #include #include #include using namespace std;const int INF = 1e9;const int MAX = 300 + 5;int N, M, Q;int g[MAX][MAX];bool mark[MAX];void init(){ for (int i = 0; i < N; i++) { g[i][i] = 0; // for (int j = i + 1; j < N; j++) // 这样就比较简洁 { g[i][j] = g[j][i] = INF; } } memset(mark, 0, sizeof mark);}void floyd_k(int k){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (g[i][k] != INF && g[k][j] != INF && g[i][k] + g[k][j] < g[i][j]) { g[i][j] = g[i][k] + g[k][j]; } } }}int main(){ int a, b, c; for (int cnt = 1; ~scanf("%d%d%d", &N, &M, &Q); cnt++) { if (!N && !M && !Q) break; init(); for (int i = 0; i < M; i++) { scanf("%d%d%d", &a, &b, &c); g[a][b] = min(g[a][b], c); } if (cnt != 1) printf("\n"); printf("Case %d:\n", cnt); for (; Q--;) { scanf("%d", &a); if (a == 0) { scanf("%d", &b); if (mark[b]) printf("ERROR! At point %d\n", b); else { mark[b] = true; floyd_k(b); } } else { scanf("%d%d", &b, &c); if (!mark[b] || !mark[c]) printf("ERROR! At path %d to %d\n", b, c); else if (g[b][c] == INF) printf("No such path\n"); else printf("%d\n", g[b][c]); } } //printf("\n"); } return 0;}