FZYZOJ 1773(最短路)

FJYZOJ 1773
一个点无法到达后使一条路径的最短路径变化,那么这个点一定在这条路径的“中转点”上,所以我们FLoyd,找出最终的中转点,就是重要的点。但是如果有几个点都可以作为最终的中转点,那么这几个点都不是重要的。

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
47
48
49
50
51
52
53
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200 + 5, INF = 1000000000;
int G[MAXN][MAXN], upt[MAXN][MAXN], n, m, mk[MAXN];
void clean() {
for (int i=1;i<=n;i++) {
mk[i] = 0;
for (int j=1;j<=n;j++) G[i][j] = INF, upt[i][j] = 0;
}
}
void solve() {
clean();
for (int i=1;i<=m;i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (G[a][b] > c) G[a][b] = G[b][a] = c;
}
for (int k=1;k<=n;k++) {
for (int j=1;j<=n;j++) {
for (int i=1;i<=n;i++) {
if (k != i && k != j && i != j) {
if (G[i][j] > G[i][k] + G[k][j]) {
G[i][j] = G[i][k] + G[k][j];
upt[i][j] = k;
} else if (G[i][j] == G[i][k] + G[k][j]) upt[i][j] = INF;
}
}
}
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (upt[i][j] == INF) continue;
mk[upt[i][j]] = 1;
}
}
bool flag = false;
for (int i=1;i<=n;i++) if (mk[i]) printf("%d ", i), flag = true;
if (!flag) printf("No important cities.");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
fclose(stdin); fclose(stdout);
return 0;
}

题目描述

小A的老师给小A布置了这样一份作业:某个城市x是“重要”的,当且仅当x不能通过时a->b的最短路径的值改变了(ab不等于x),现在告诉你N个城市和M条连接城市之间的路径,求出哪些点是重要的。小A忙着去找小N所以没空做作业。请帮助小A算出哪些城市是重要的。如果不存在就输出”No important cities.”给出的是一个无向图。

输入格式

第一行两个整数N, M,N表示城市数,M表示城市间的道路数。

以下N行,每行三个整数a,b,c。表示城市a到城市b之间存在一条长度为c的道路。

两个城市间可能存在多条道路。

输出格式

一行,按升序输出哪些城市是重要的,2个数中间用空格分开

输入样例

4 4
1 2 1
2 3 1
4 1 2
4 3 2
输出样例

2
数据规模与约定

60%数据中N<=100

100%数据中N<=200,M<=N* N,1<=c<=10000

------ 本文结束 ------