Shortest paths - interesting graph problems
Change of Scenery
Every day you drive to work using the same roads as it is the shortest way. This is efficient, but over time you have grown increasingly bored of seeing the same buildings and junctions every day. So you decide to look for different routes. Of course you do not want to sacrifice time, so the new way should be as short as the old one. Is there another way that differs from the old one in at least one street?
The first line starts with three integers n, m and k (1 ≤ k ≤ n ≤
104, 0 ≤ m ≤
106), where n is the number of junctions, m is the number of streets in your city and k is the number of junctions you pass every day.
The next line contains k integers, the (1-based) indices of the junctions you pass every day. The first integer in this line will always be 1, the last integer will always be n. There is a shortest path from 1 to n along the k junctions given.
m lines follow. The i-th of those lines contains three integers
ci and describes a street from junction
ai to junction
bi of length
ci (1 ≤
bi ≤ n, 1 ≤
104). Streets are always undirected.
Note that there may be multiple streets connecting the same pair of junctions. The shortest path given uses for every pair of successive junctions a and b a street of minimal length between a and b.
Print one line containing "yes" if there is another way you can take without losing time and "no" otherwise.
3 3 3 1 2 3 1 2 1 2 3 2 1 3 3
4 5 2 1 4 1 2 2 2 4 1 1 3 1 3 4 2 1 4 2