WOSS Dual Olympiad 2023 Team Round P3: Choosing Edges

View as PDF

Submit solution


Points: 12
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem type

You have an unweighted directed graph with N nodes and M edges. The ith edge goes from node ui to vi. You also have K other directed edges which are not currently in the graph. The ith edge in this set has a color ci and goes from node ui to vi. You may add either 1 or 2 edges from this set onto the graph. If you add 2 edges, they must have different colors. Determine the minimum distance from node 1 to node N after adding the optimal edges, or output -1 if node N is still unreachable.

Constraints

1N,M5×103

1K106

1ui,viN

1ci109

Input Specification

The first line of input contains 3 space-separated integers N, M, and K.

The next M lines each contain 2 space-separated integers, ui and vi.

The next K lines each contain 3 space-separated integers, ui, vi, and ci.

Output Specification

Output a single integer, the minimum distance from node 1 to node N after adding the optimal 2 edges.

If it is impossible to reach node N from node 1, output -1.

Sample Input

Copy
7 7 5
1 2
2 3
1 4
4 5
3 5
6 5
7 6
1 5 1
3 7 3
3 4 3
1 3 2
5 7 1

Sample Output

Copy
2

Sample Input 2

Copy
9 4 7
1 2
2 3
3 4
4 9
1 8 1
8 9 1
1 7 1
7 9 1
1 6 1
6 5 2
5 9 3

Sample Output 2

Copy
4

Sample Input 3

Copy
4 2 2
1 3
3 2
1 2 1
2 4 1

Sample Output 3

Copy
3

Comments

There are no comments at the moment.