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