学步园

题目：Shortest Path

题意：一张图有n个顶点m条边，现在给q个查询。查询0 x，标记顶点x。查询1 x y，查找x和y之间通过标记点的最短路。

题解：每次查询做一次floyd，对floyd还是理解的不够透彻。不是很明白原理。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const int maxn = 310;
const int inf = 99999999;
int n, m, q;
int ans[maxn][maxn];
int mark[maxn];
int floyd(int x){
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < n; j ++){
			ans[i][j] = min( ans[i][j], ans[i][x] + ans[x][j]);
		}
	}
}
int main(){
	int x, y, vel, t= 1;
	while(1){
		scanf("%d%d%d",&n,&m,&q);
		if( (n|m|q) == 0) break;
		
		for(int i = 0; i < maxn; i ++){
			for(int j = 0; j < maxn; j ++){
				ans[i][j] = inf;
				ans[i][i] = 0;
			}
		}
		
		memset(mark, 0, sizeof(mark));
		while(m --){
			scanf("%d%d%d",&x,&y,&vel);
			ans[x][y] = min(ans[x][y], vel);
		}
		if( t>1) printf("\n");
		printf("Case %d:\n",t++); 
		while(q --){
			scanf("%d",&vel);
			if( vel == 1 ){ 
				scanf("%d%d",&x,&y);
				if( mark[x] && mark[y] ) {
					if( ans[x][y] >= 99999999 ) printf("No such path\n");  
					else printf("%d\n",ans[x][y]);
				}
				else printf("ERROR! At path %d to %d\n",x,y);
			}
			else {
				scanf("%d",&x);
				if( mark[x] ) printf("ERROR! At point %d\n",x);
				else {
					mark[x] = 1;
					floyd(x);
				}
			}
		}
	}
	return 0;
}