web analytics

NOIP模拟赛-BZOJ3538-坑爹的GPS spfa

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 524288kB
描述
有一天,FJ买了一辆车,但是,他一手下载了两个GPS系统。好了现在麻烦的事情来了,GPS有一个功能大概大家也知道,如果FJ没有按照GPS内置地图的最短路走,GPS就会报错来骚扰你。现在FJ准备从他的农舍(在1这个点)开车到他的谷屋(N这个点)。FJ给了你两个GPS系统内置地图的信息,他想知道,他最少会听到多少次报错(如果FJ走的路同时不满足两个GPS,报错次数+2)。

输入
第一行:两个整数N和K:N表示有FJ的谷屋在哪,同时保证GPS内置地图里的点没有超过N的点。K表示GPS内置地图里的路有多少条,如果两个点没有连接则表明这不是一条通路。
接下来K行,每行4个整数X、Y、A、B,分别表示从X到Y在第一个GPS地图里的距离是A,在第二个GPS地图里的是B。注意由于地形等其他因素,GPS给出的边是有向边。
输出
一个整数,表示FJ最少听到的报错次数。
样例输入
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
样例输出
1
提示
FJ选择的路线是1 2 4 5,但是GPS 1认为的最短路是1到3,所以报错一次,对于剩下的2 4 5,两个GPS都不会报错。

N<=10000,K<=50000。数据保证所有的距离都在2^31-1以内。 分析: 3遍最短路。 第1,2遍反向最短路。求每个点向下的最优的路径。 根据前两次的spfa统计每条路径的报警数。 第三遍spfa的边权值为报警数。 统计最后的报警数就好了。

Post a Comment

You must be logged in to post a comment.