luogu-P1831-重要的城市

题目链接


跑一次floyd即可,新建一个数组c,如果i到j的最短路能被k更新,那么说明最短路一定会经过k,所以c[i][j]保存一下k,如果更新过程发现存在一个相等的更新条件,说明最短路有多条,这个时候就可以删去c[i][j]里面的数.

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
46
#include<bits/stdc++.h>
using namespace std;

int n, m;
int f[209][209], cnt[209][209];
bool ans[209];
int tot;

int main(){
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; i++){
f[i][i] = 0;
}
for(int i = 1; i <= m; i++){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
f[x][y] = w;
f[y][x] = w;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
if(i == k) continue;
for(int j = 1; j <= n; j++){
if(i == j || j == k) continue;
if(f[i][k] + f[k][j] < f[i][j]){
f[i][j] = f[i][k] + f[k][j];
cnt[i][j] = k;
}
else if(f[i][k] + f[k][j] == f[i][j]){
cnt[i][j] = 0;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ans[cnt[i][j]] = 1;
}
}
for(int i = 1; i <= n; i++){
if(ans[i]) printf("%d ", i), tot++;
}
if(tot == 0) printf("No important cities.");
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×