題目地址：http://acm.hdu.edu.cn/showPRoblem.php?pid=3631

思路：Floyd，對(duì)于已求出最短路的圖，若增加一點(diǎn)k及相應(yīng)的邊，則只需將k當(dāng)做中間節(jié)點(diǎn)更新點(diǎn)u與點(diǎn)v的距離即可。因此，每增加一個(gè)標(biāo)記點(diǎn)時(shí)，則將標(biāo)記點(diǎn)當(dāng)做中間節(jié)點(diǎn)更新最短路徑，由于點(diǎn)數(shù)只有300，時(shí)間上可以承受。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn=300+50;const int INF=0x3f3f3f3f;int n,m,q;int flag[maxn];LL g[maxn][maxn];void Floyd(int k){    for(int i=0; i<n; i++)    {        for(int j=0; j<n; j++)        {            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);        }    }}void init(){    for(int i=0; i<n; i++)    {        g[i][i]=0;        for(int j=0; j<n; j++)            if(i!=j) g[i][j]=INF;    }    memset(flag,0,sizeof(flag));}int main(){    int cas=0;    while(scanf("%d%d%d",&n,&m,&q)!=EOF&&n)    {        cas++;        if(cas!=1) printf("/n");        printf("Case %d:/n",cas);        init();        for(int i=0; i<m; i++)        {            LL w;            int x,y;            scanf("%d%d%lld",&x,&y,&w);            g[x][y]=min(g[x][y],w);        }        for(int i=0; i<q; i++)        {            int cmd,x,y;            scanf("%d",&cmd);            if(cmd==0)            {                scanf("%d",&x);                if(flag[x]) printf("ERROR! At point %d/n",x);                else                {                    Floyd(x);                    flag[x]=1;                }            }            else            {                scanf("%d%d",&x,&y);                if(!flag[x]||!flag[y]) printf("ERROR! At path %d to %d/n",x,y);                else                {                    if(g[x][y]>=INF) printf("No such path/n");                    else printf("%lld/n",g[x][y]);                }            }        }    }    return 0;}