codeforce-601A. The Two Routes(最短路)

题意：

给你N个点表示N个站，有汽车和火车，汽车只能走公路，火车只能走铁路。

然后给你M条双向路，代表这两个点之间有铁路连接。

然后告诉你如果两个点之间没有铁路，那么就是公路连接。

问你汽车和火车都到达目的地所要的最小时间是多少(两种交通工具不能同时到达同一个城市除了目的地)。

如果有一种交通工具不能到达就输出-1；

思路:

如果两两点之间都是铁路，那么就没有公路，那么汽车不能到达，这时-1；

如果不是这种情况那么要么有铁路连接起点终点，要么有公路，所以两者间必有一个为1，

所以求另一个的最短路就行（肯定不会相撞）。（求两次最短路也行）。

复杂度N²;

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<vector>

 6 #include<queue>

 7 #include<cstdio>

 8 #include<string.h>

 9 void dj(int n);

10 const int V=99999999;

11 typedef struct pp

12 {

13     int x;

14     int y;

15 } ss;

16 using namespace std;

17 int flag[500];

18 int jj[500][500];

19 int  d[500];

20 int main(void)

21 {

22     int n,i,j,k,p,q,N,M;

23     while(scanf("%d %d",&N,&M)!=EOF)

24     {

25         memset(flag,0,sizeof(flag));

26         for(i=0; i<450; i++)

27         {

28             for(j=0; j<450; j++)

29             {

30                 jj[i][j]=V;

31             }

32         }

33         for(i=0; i<M; i++)

34         {

35             scanf("%d %d",&p,&q);

36             jj[p][q]=1;

37             jj[q][p]=1;

38         }

39         dj(N);

40         int ss=d[N];

41         for(i=0; i<450; i++)//求汽车的路径

42         {

43             for(j=0; j<450; j++)

44             {

45                 if(jj[i][j]==V)

46                 {

47                     jj[i][j]=1;

48                 }

49                 else jj[i][j]=V;

50             }

51         }

52         dj(N);

53         int vv=d[N];

54         int uu=max(vv,ss);

55         if(uu>=V)

56         {

57             printf("-1\n");

58         }

59         else printf("%d\n",uu);

60

61     }

62     return 0;

63 }

64

65 void dj(int n)//最短路N2算法

66 {

67     fill(d,d+n+1,V);

68     fill(flag,flag+n+1,0);

69     d[1]=0;

70     int i,j,k,p,q;

71     while(true)

72     {

73         int l=-1;

74         for(i=1; i<=n; i++)

75         {

76             if(flag[i]==0&&(l==-1||d[i]<d[l]))

77             {

78                 l=i;

79             }

80         }

81         if(l==-1)

82         {

83             break;

84         }

85         flag[l]=1;

86         for(i=1; i<=n; i++)

87         {

88             d[i]=min(d[i],d[l]+jj[l][i]);

89         }

90     }

91

92 }

巴特西

codeforce-601A. The Two Routes(最短路)

最新文章

热门文章