526互联

Shortest time（最短时间）

发布时间 2023-04-23 19:30:20作者: nasia

这题怎么这么难啊(恼

 

有若干个城市，它们之间有道路连通，可以互相到达，从一个城市到另一个城市时间为1。现在给出起点城市A,终点城市B，和N条道路。
问从A到B最短时间。

input
    第一行A，B，N（A,B,N<=30），B为最大城市标号
    接下来N行，每行两个数x,y，表示城市x和城市y有道路相连。
output
    最短时间
__的题目：

 

 

 

 

样例

样例输入1

 

1 7 9
1 2
1 4
2 3
3 5
4 5
4 6
1 6
6 7
5 7

 

样例输出1

 

2

 

tips:城市1可以通过1——6——7到达城市7，花费最短时间为2.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a,b,n,d[40],vis[40];
 4 bool city[40][40];
 5 queue<int> q;
 6 void bfs()
 7 {
 8     q.push(a);
 9     vis[a]=1;
10     d[a]=0;
11     while(!q.empty())
12     {
13         int x=q.front();
14         q.pop();
15         vis[x]=0;
16         for(int i=1;i<=b;i++)
17         {
18             if(city[x][i]&&!vis[i])
19             {
20                 q.push(i);
21                 vis[i]=1;
22                 d[i]=d[x]+1;
23                 if(i==b)
24                 {
25                     cout << d[i];
26                     exit(0);
27                 }
28             }
29         }
30     }
31 }
32 int main()
33 {
34     cin >> a >> b >> n;
35     for(int i=1;i<=n;i++)
36     {
37         int x,y;
38         cin >> x >> y;
39         city[x][y]=1;
40         city[y][x]=1;
41     }
42     bfs();
43     return 0;
44 }