problem description
Xiaoming and Xiaofang go out to play in the country. Xiaoming is in charge of driving and Xiaofang is in charge of navigation.
Xiaofang divides the possible roads into main roads and paths. The main road is easier to walk, and Xiaoming will increase his fatigue by 1 per kilometer. The path is not easy to walk, if you continue to take the path, Xiaoming"s fatigue value will increase rapidly, continuous s km Xiaoming will increase the degree of fatigue of S2.
for example: there are 5 intersections, the path is from No.1 to No.2, from No.2 to No.3 is a trail, from No.3 to No.4 is an avenue, and from No.4 to No.5 is a trail. The distance between adjacent intersections is 2 kilometers. If Xiaoming goes from intersection 1 to intersection 5, the total fatigue value is (2 / 2) 2 / 2 / 22 / 16 / 2 / 4 / 22.
now that Xiaofang has got the map, please help her plan a driving route to minimize the fatigue of driving Xiaoming.
input format
the first line of input contains two integers n and m, representing the number of intersections and the number of roads, respectively. The intersection is numbered from 1 to n. Xiaoming needs to drive from intersection 1 to intersection n.
the next m lines describe the road, with each line containing four integers t, a, b, c, representing a two-way road of type t connecting two junctions an and b, with a length of c kilometers. Where t is 0 for the main road and t for 1 for the path. Make sure that Junction 1 and Junction n are connected.
output format
outputs an integer indicating the fatigue degree of Xiaoming under the optimal route.
sample input
6 7
1 123
1 232
0 1330
0 3420
0 430
1 356
1 561
sample output
76
sample description
from 1 to 2, and then to 3, the fatigue degree is 5225, and then from 3 roads through 4 to 5, the fatigue degree is 20 years. The total is 76.
data size and convention
for 30% evaluation use cases, 1 n 8 score 1 m 10;
for the other 20% evaluation use cases, there are no trails;
for the other 20% evaluation use cases, all trails do not intersect;
for all evaluation use cases, 1 n 500quot 1 m 105pl 1 a, b n quotient t is 0 or 1pi c 105i. Make sure the answer does not exceed 106.
look at many people on the Internet using the Dijstra algorithm. If you encounter a path and keep finding the road, add up the square of this section, plus the weight of the previous point, to serve as the minimum distance of the path point, and you can also submit it. I did the same thing, but there is a problem when I think about it. This algorithm includes the new node and thinks that he must have come from the node route that has already been included. Well, if the last node comes by two paths, and if a road comes, then the distance is slightly longer, then another path adds up to a square greater than the road plus the path, that is to say, the weight of the previous point may only be the smallest before, and can"t be used.
Chinese is not very good. That"s probably what it means. I"d like to ask how to improve it