P3905 道路重建

    • 1.4K通过
    • 3K提交
  • 题目提供者 Satoshi_
  • 评测方式 云端评测
  • 标签 SPFA 图论 最短路 队列 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    从前,在一个王国中,在$n$个城市间有$m$条道路连接,而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后,有$d$条道路被破坏了。国王想要修复国家的道路系统,现在有两个重要城市$A$和$B$之间的交通中断,国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使$A$与$B$之间的连接恢复,并要求修复的道路长度最小。

    输入输出格式

    输入格式:

    输入文件第一行为一个整数$n$($2<n≤100$),表示城市的个数。这些城市编号从$1$到$n$。

    第二行为一个整数$m$($n-1≤m≤\frac{1}{2} n(n-1)$),表示道路的数目。

    接下来的$m$行,每行$3$个整数$i,j,k$($1≤i,j≤n,i≠j,0<k≤100$),表示城市$i$与$j$之间有一条长为$k$的道路相连。

    接下来一行为一个整数$d$($1≤d≤m$),表示战后被破坏的道路的数目。在接下来的$d$行中,每行两个整数$i$和$j$,表示城市$i$与$j$之间直接相连的道路被破坏。

    最后一行为两个整数A和B,代表需要恢复交通的两个重要城市。

    输出格式:

    输出文件仅一个整数,表示恢复$A$与$B$间的交通需要修复的道路总长度的最小值。

    输入输出样例

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