题解

1 条题解

  • 0
    @ 2025-06-09 15:28:18

    三次最短路:
    第一次:对于B系统建立反向图,从n出发跑一次最短路,得到dis1[i],表示B系统中n到i的最短路长度(在正向图上就是i到n的最短路长度)
    第二次:对于G系统建立反向图,从n出发跑一次最短路,得到dis2[i],表示G系统中n到i的最短路长度(在正向图上就是i到n的最短路长度)

    第三次:对于图(B或G系统的反向图的边)的任意每条边<x,y>:
    如果t[x][y]+dis1[y]==dis1[x],则B系统在这条边上不会警告,否则会警告;
    如果w[x][y]+dis2[y]==dis2[x],则G系统在这条边上不会警告;否则会警告;
    据此,我们建立一张新图,对于原图的边<x,y>,加入到新图中,权值为:0,1或2,具体如下:
    如果两个系统都不会发出警告,权值为0;
    如果只有一个系统都不会发出警告,权值为1;
    如果两个系统都会警告,权值为2.

    建立新图后,从n跑一次最短路dist[i],则dist[1]就是n到1的最短路径,即最少警告次数的路径。

  • 1

信息

ID
2252
难度
9
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
5
上传者