「NOIP模拟赛」坑爹的GPS

2014年7月3日2,0762

坑爹的GPS(gpsduel.c/.cpp/.pas)

有一天,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,至于路有多少条自己算吧。数据保证所有的距离都在2^31-1以内。

题解

三次最短路。。。

 

说点什么

提醒
avatar
caoyi0905
caoyi0905

http://acdream.info/problem?pid=1007 在这题上跪了一遍又一遍。。求大神秒掉~

De℃,.: )
De℃,.: )

这题模数是1e10+7= =WA了好久