1 条题解
-
0
何老师 (root) LV 0 MOD @ 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