HDu 3631(floyd思想の運用)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3631
構想:タグの点でしか更新できないため、任意の2点間の最短距離が要求されるため、floydが最も適切であることは明らかである.

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<queue>

 6 #include<vector>

 7 using namespace std;

 8 #define MAXN 333

 9 #define inf 1<<30

10 bool mark[MAXN];

11 int map[MAXN][MAXN];

12 int N,M,Q;

13 

14 void Floyd(int x){

15     for(int i=0;i<N;i++){

16         for(int j=0;j<N;j++){

17             if(map[i][x]!=inf&&map[x][j]!=inf&&map[i][j]>map[i][x]+map[x][j]){

18                 map[i][j]=map[i][x]+map[x][j];

19             }

20         }

21     }

22 }

23 

24 

25 int main(){

26     int _case=1,u,v,w,x,y,flag;

27     while(~scanf("%d%d%d",&N,&M,&Q),(N+M+Q)){

28         if(_case>1)puts("");

29         for(int i=0;i<N;i++){

30             map[i][i]=0;

31             for(int j=i+1;j<N;j++){

32                 map[i][j]=map[j][i]=inf;

33             }

34         }

35         for(int i=1;i<=M;i++){

36             scanf("%d%d%d",&u,&v,&w);

37             if(w<map[u][v])map[u][v]=w;

38         }

39         memset(mark,false,sizeof(mark));

40         printf("Case %d:
",_case++);

41         while(Q--){

42             scanf("%d",&flag);

43             if(flag==0){

44                 scanf("%d",&x);

45                 if(mark[x]){ printf("ERROR! At point %d
",x);continue; }

46                 mark[x]=true;

47                 Floyd(x);

48             }else {

49                 scanf("%d%d",&x,&y);

50                 if(!mark[x]||!mark[y]){

51                     printf("ERROR! At path %d to %d
",x,y);

52                 }else if(map[x][y]<inf){

53                     printf("%d
",map[x][y]);

54                 }else 

55                     puts("No such path");

56             }

57         }

58     }

59     return 0;

60 }

View Code