P2185 公路通行税

    • 54通过
    • 565提交
  • 题目提供者 mhlwsk
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在PALMIA国家内,有N个城市由公路相连(每条公路恰好双向连接两个城市)。经由一条公路或多条公路,从任一城市出发可以到达其余各个城市。直到今年,公路上才要征收公路通行税。在每条公路的中间,有一征税员,从每一辆经由此路的车收取 1 PALMIA COIN(1PC)。

    政府官员决定减少收税员而推行公路印花。如果一辆车欲进入一条公路,就必须将这张印花贴在窗上。

    政府官员决定:一年的公路印花的价值相当于在两个最远城市之间进行100次旅行所需的费用。两个城市之间的距离是从一个城市到达第二个城市所需经过的最少数目的公路数。

    你的任务是编写一个程序计算出公路印花的价值。

    输入输出格式

    输入格式:

    输入文件中包含几组数据。每组的第一行包括整数N和M(中间被一个空格隔开),N是该国家中城市的数目,M是公路的数目(1≦N≦1000,1≦M≦25000)。城市由整数进行编号,从1到N。接下来的M行,每行均包含一对整数A,B(1≦A,B≦N),中间由一空格隔开,代表在城市A与B之间有一条公路。在最后一组数后仅有一行,是两个0,中间被一空格隔开。

    输出格式:

    对输入文件中的各组数据,输出文件中包含一行,表示公路印花的价值。

    输入输出样例

    输入样例#1: 复制
    4 4
    1 2
    2 3
    4 2
    3 4
    0 0
    输出样例#1: 复制
    200
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。