题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3631
题目中给定两种操作：一种是将某一个点做标记，一种是查询两点之间经过标记点的最小值。由于智能经过标记点，而且两点之间如果有最短的路径的话一定是通过这些标记点作为中转点的，所以可以在每次新标记一个点的时候用这个点去松弛每个点对之间的distance。注意是两个样例输出之间才有空行还有点是从0开始的。
由这道题我们也可以知道floyd算法可以解决动态加可松弛点以及动态查询最短路的功能，因为对于每一个新给出的点，都可以在O(n^2)时间内判断（i,j）两点之间的最短路是否可以用这个点作为中转进行松弛，唯一的遗憾就是floyd时间复杂度非常高，对于这道点的数量小于等于300的尚且还是能处理的。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch==‘-‘)w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-‘0‘,ch=getchar(); 25 return ans*w; 26 } 27 const int maxn=305; 28 int n,m,t; 29 int dis[maxn][maxn],vis[maxn]; 30 void floyd(int k) 31 { 32 f(i,0,n-1) 33 f(j,0,n-1) 34 { 35 if(dis[i][j]>dis[i][k]+dis[k][j])//dis[i][k]和dis[k][j]都是利用之前标记的点在当前的最短的路径长度 36 dis[i][j]=dis[i][k]+dis[k][j]; 37 } 38 } 39 int main() 40 { 41 //freopen("input.txt","r",stdin); 42 //freopen("output.txt","w",stdout); 43 std::ios::sync_with_stdio(false); 44 int cnt=0; 45 while(scanf("%d%d%d",&n,&m,&t)!=EOF) 46 { 47 if(n==0&&m==0&&t==0)break; 48 mem(vis,0); 49 f(i,0,n-1) 50 f(j,0,n-1) 51 { 52 if(i==j)dis[i][j]=0;//本题存在自身的环 53 else dis[i][j]=inf; 54 } 55 int u,v,w; 56 while(m--) 57 { 58 u=read(),v=read(),w=read(); 59 if(dis[u][v]>w)dis[u][v]=w; 60 } 61 if(cnt)pf("\n"); 62 pf("Case %d:\n",++cnt); 63 while(t--) 64 { 65 u=read(); 66 if(u==0) 67 { 68 v=read(); 69 if(vis[v])pf("ERROR! At point %d\n",v); 70 else 71 { 72 vis[v]=1; 73 floyd(v);//在路径中加上一个可松弛的点 74 } 75 } 76 else 77 { 78 v=read(),w=read(); 79 if(!vis[v]||!vis[w])pf("ERROR! At path %d to %d\n",v,w); 80 else if(dis[v][w]==inf)pf("No such path\n");//记住加else，否则会输出两种情况，大意了 81 else pf("%d\n",dis[v][w]); 82 } 83 } 84 } 85 }
原文：https://www.cnblogs.com/randy-lo/p/12590216.html