Rockdu's Blog

题目描述

参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。

他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。

jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。

输入输出格式

输入格式：

第一行两个整数N,M,N为城市数，M为道路数

接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度

输出格式：

一行，按递增次序输出若干的数，表示重要的城市。

输入输出样例

4 4
1 2 1
2 3 1
4 1 2
4 3 2

2

说明

30%的数据：$N\le 20$；

60%的数据：$N\le 100$；

100%的数据：N≤200,M≤2N×(N−1)​,0<c≤10000。c即路的长度。

保证不出现重边和自环

感谢@赵昕鹏 和@qq2477259579 提供程序

如果没有点的话需要输出一行

“No important cities.”

去掉引号

大概要真正理解floyd才可以理解这道题。

考虑任意两点的最短路，floyd算法的过程相当于是这两点之间的最短路不断变得连续的过程。

那么这道题就好做了，floyd每一次将两条路径的信息合并成一条，我们对每一条路径记录最后更新它的点是哪一个，考虑对于一条最短路来说，所有更新它的点都可以递归到每一次更新过程中去找到。

因此我们直接看没有被任何一条最短路记录的点，除此之外去除多次被更新相同距离的点就好了。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 3e2 + 5;
int dp[maxn][maxn], mul[maxn][maxn];
int ans[maxn], n, m, u, v, w, flag;

int main() {
    memset(dp, 0x3f, sizeof(dp));
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d%d", &u, &v, &w), dp[u][v] = dp[v][u] = w;
    for(register int k = 1; k <= n; ++k) {
        for(register int i = 1; i <= n; ++i)
            for(register int j = 1; j <= n; ++j) {
                if(i == j || j == k) continue;
                if(dp[i][j] == dp[i][k] + dp[k][j]) {
                    mul[i][j] = -1;
                }
                if(dp[i][j] > dp[i][k] + dp[k][j]) {
      				mul[i][j] = k, dp[i][j] = dp[i][k] + dp[k][j];
      			}
            }
    }
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            if(~mul[i][j]) 
                ans[mul[i][j]] = 1;
    for(register int i = 1; i <= n; ++i)
        if(ans[i]) printf("%d ", i), flag = 1;
    if(!flag) printf("No important cities.");
    return 0;
}