当前位置：首页 > news >正文

最少换乘

news 来源：原创 2024/5/3 12:15:51

题解 : 给你几班车 , 主人公想从 1 到 N 问你需要换乘几辆车 ?　　　　对于这种有去无回的图 , 不需要做特殊处理 .

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<iostream>
 5 #include<limits.h>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #include<stack>
11 #include<string>
12 #include<sstream>
13 #include<map>
14 #include<cctype>
15 using namespace std;      //最少换乘  ,  由于是单源最短路径的求解 还是不用 Floyd 了 , 以免超时 , 而且已经证明这一道题上  Floyd是 Dijkstra的 100倍
16 int visited[505],dis[505],a[505][505];
17 int Dijkstra(int n)
18 {
19     for(int i=1;i<=n;i++)       //  将 和 1   连接 , 的储存到dis中
20         dis[i]=a[1][i];
21     dis[1]=0;
22     visited[1]=1;
23     for(int i=1;i<=n;i++)   // 一共有 七个站点
24     {
25         int v,minn=INT_MAX;
26         for(int j=1;j<=n;j++)
27         {
28             if(minn>dis[j]&&!visited[j])
29             {
30                 minn=dis[j];
31                 v=j;
32             }
33         }
34         visited[v]=1;
35         for(int j=1;j<=n;j++)
36         {
37             if(!visited[j]&&a[v][j]!=INT_MAX&&dis[v]!=INT_MAX&&dis[j]>dis[v]+a[v][j])        //  用  INT_MAX的 话存在一个问题就是只要一 + 就从最大值变成最小值 所以   用INT_MAX的话 需要谨慎对待相加问题
38             {
39                 dis[j]=dis[v]+a[v][j];
40             }
41         }
42     }
43     return dis[n];
44 }
45 int main()
46 {
47     int t,n,m;
48     string road;
49     scanf("%d",&t);
50     while(t--)
51     {
52         scanf("%d%d",&m,&n);
53         for(int i=0;i<=n;i++)
54         {
55             dis[i]=INT_MAX;
56             for(int j=0;j<=n;j++)
57                 a[i][j]=INT_MAX;
58         }
59         memset(visited,0,sizeof(visited));
60         if(t!=0)
61             getchar();
62         for(int i=0;i<m;i++)
63         {
64             int sum=0;
65             getline(cin,road);   // 第一行数据
66             int q=0;
67             for(int j=0;j<road.size();j++)
68             {
69                 if(road[j]==' ')
70                 {
71                     dis[q++]=sum;
72                     sum=0;
73                     continue;
74                 }
75                 sum=sum*10+road[j]-'0';
76             }
77             dis[q++]=sum;
78             for(int w=0;w<q;w++)
79                 for(int j=w+1;j<q;j++)
80                 a[dis[w]][dis[j]]=1;   //  一路车的 换乘次数就是 1 .   在每个 可以直接到达的地方 都是 1 , 如果需要倒车的话 在 +1
81         }
82         int e=Dijkstra(n);
83         if(e==INT_MAX)
84             printf("NO\n");
85         else
86             printf("%d\n",e-1);
87     }
88     return 0;
89 }