P2103 道路值守

    • 103通过
    • 324提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 图论 搜索 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms-3000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

    特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

    显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

    输入输出格式

    输入格式:

    第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

    接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

    两个不同地点之间不会有超过一条道路。

    输出格式:

    输出一行,包含 N (N-1)/2 个整数

    其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

    输入输出样例

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

    说明

    【数据规模】

    对于30%的数据,保证 N≤50

    对于60%的数据,保证 N≤100

    对于100%的数据,保证 N≤500。

    【时空限制】

    5s/128M

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