P1841 [JSOI2007]重要的城市

    • 126通过
    • 465提交
  • 题目提供者lych
  • 标签 Floyd 动态规划,动规,dp 图论 各省省选 2007 江苏
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    参加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%的数据:$N\le 20$;

    60%的数据:$N\le 100$;

    100%的数据:$N\le 200,M\le \frac{N\times (N-1)}{2},0<c\le 10000$。c即路的长度。

    保证不出现重边和自环

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

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

    “No important cities.”

    去掉引号

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。