UVa 10959
題目
http://domen111.github.io/UVa-Easy-Viewer/?10959
我們可以把 Don Giovanni 當作是所有人的起點
所有跟 Don Giovanni 跳過舞的人都距離 Don Giovanni $1$
所有跟距離 Don Giovanni $n$ 的人跳過舞，則他的距離會變成 $n+1$
現在告訴你有 $P$ 個人，並且有 $D$ 對跳舞的人，求每個人到 Don Giovanni 的距離
想法
可以把所有跳舞的人之間連上一條邊
然後從 Don Giovanni $(0)$ 開始，把所有邊都走過一遍
因為要的是距離，可以用 BFS ，如此一來第一次走到的距離就是 $1$，第二次距離就是 $2$，以此類推
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<iostream>
using namespace std;
int t, P, D, que[1005], dis[1005], cur;
bool edge[1005][1005];
void BFS(){
que[0] = 0;
dis[0] = 0;
for(int i=0, j=1 ; i<j ; i++){
cur = que[i];
for(int nxt=0 ; nxt<P ; nxt++){
if(edge[cur][nxt] && dis[nxt] > dis[cur] + 1){
dis[nxt] = dis[cur] + 1;
que[j] = nxt;
j++;
}
}
}
}
int main(){
cin>>t;
for(int i=0 ; i<t ; i++){
if(i) cout<<"\n";
for(int j=0 ; j<1005 ; j++){
dis[j] = 1e9+10;
for(int k=0 ; k<1005 ; k++){
edge[j][k] = false;
}
}
cin>>P>>D;
for(int j=0, a, b ; j<D ; j++){
cin>>a>>b;
edge[a][b] = edge[b][a] = true;
}
BFS();
for(int i=1 ; i<P ; i++){
cout<<dis[i]<<"\n";
}
}
return 0;
}
|
時間複雜度分析
每筆測資輸入時間複雜度為 $O(D)$
每筆測資 BFS 時間複雜度為 $O(P)$
總時間複雜度為 $O(t(D + P))$