题目描述
参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。
同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。
他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。
jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。
输入输出格式
输入格式：
第一行两个整数N,M,N为城市数，M为道路数
接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度
输出格式：
一行，按递增次序输出若干的数，表示重要的城市。
输入输出样例
说明
30%的数据：N\le 20N≤20 ；
60%的数据：N\le 100N≤100 ；
100%的数据：N\le 200,M\le \frac{N\times (N-1)}{2},0<c\le 10000N≤200,M≤2N×(N−1),0<c≤10000 。c即路的长度。
保证不出现重边和自环
spfa+最短路树
#include <bits/stdc++.h>
using namespace std;
#define maxn 40010
typedef long long ll;
#define inf 2147483647
#define ri register int
//链式前向星
struct edge {
int to, next, w;
} e[maxn];
int tot = ;
int head[maxn];
void add(int u, int v, int w) {
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
e[tot].w = w;
}
// spfa
queue<int> que;
bool vis[maxn];
int dis[maxn];
//最短路树
int cnt[maxn];//记录相同最短路径长度个数
int fa[maxn]; //记录最短路径上的父亲 int n, m, x;
bool ans[maxn]; int main() {
ios::sync_with_stdio(false);
// freopen("test.txt", "r", stdin);
// freopen("outout.txt","w",stdout);
cin >> n >> m;
for (int i = ; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w), add(v, u, w);
}
for (int s = ; s <= n; s++) {
memset(fa, , sizeof(fa));
memset(dis, , sizeof(dis));
memset(cnt, , sizeof(cnt));
memset(vis, , sizeof(vis));
dis[s] = ;
vis[s] = true;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;//与bfs不同之处，就是为了让点重复进队列，没错，就算把源点也false掉，因为dist[s]=0,也没有造成影响
for (int p = head[u]; p; p = e[p].next) {
int v = e[p].to, w = e[p].w;
if (dis[v] == dis[u] + w)
cnt[v]++;//相同路径长度个数加一
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = ;//当父亲就只有一个的时候，那么他就是爆炸点了
fa[v] = u;
if (!vis[v]) {
vis[v] = true;
que.push(v);
}
}
}
}
for (int i = ; i <= n; i++) {
if (fa[i] != s && cnt[i] == )//这里不能取源点，取源点的话就只有两个点，但必须要有三个点才满足题意
ans[fa[i]] = true;
}
}
bool flag = true;
for (int i = ; i <= n; i++)
if (ans[i])
cout << i << " ", flag = false;
if (flag)
cout << "No important cities."; return ;
}