洛谷P1841 [JSOI2007]重要的城市
? 解题记录 ? ? 洛谷 ? ? Floyd ?    2018-10-21 15:29:58    620    0    0

题目描述

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

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

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

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

输入输出格式

输入格式:

 

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
4 4
1 2 1
2 3 1
4 1 2
4 3 2
输出样例#1: 复制
2

说明

30%的数据:N20

60%的数据:N100

100%的数据:N200,M2N×(N1),0<c10000。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;
}


上一篇: 洛谷P2407 [SDOI2009]地图复原

下一篇: 洛谷P2051 [AHOI2009]中国象棋

620 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航