Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Seven Kingdoms!

By Peregrine_Falcon · Limits 500ms, 512 MB

The dragon queen just conquered the Seven Kingdoms. Initially there are N cities in “Seven Kingdoms” numbered from 1 to N.

Those cities are connected by with M directed roads. It’s possible that cities are disconnected.

After the Great(?) victory the dragon queen announced that whenever a person will go through a road he/she will receive C gold coins. Number C differ from road to road.

Just imagine what will happen if some cities will form a cyclic path! If a person is currently in city X and there is a cycle forming with this city then the person can collect infinite amount of gold coin. Which the “Iron Bank” can’t provide.

The hand of the queen Tyrion Lannister come up with a smart idea. They will select a subset of cities. Then merge those city/cities to a single city. All the roads between those cities will be destroyed.

Suppose two newly generated city is A and B . If there exists a road which leads from a city of subset A to B then there will be a road from A to B.

They will rebuild the “Seven Kingdoms” in such a way that the number of cities will be maximized and no cycle will remain.

We all know that John Snow became poor by fighting war after war. Now, he planned to start travelling through those roads and collect some money. You are a great friend of him.

He will ask you Q independent queries. For each query he will give you the city X from the city map before the reform of those cities and you’ve to tell what is the maximum amount of gold coin he can collect if he start his journey from the new city which contains the city X.

Input

The first line contains three integer numbers N , M and Q (1≤N,M≤10^5, 0≤Q≤10^5) number of the cities, number of roads and number of queries. The following M lines contains three integers U, V and C (1≤U,V≤N, 1≤C≤10^5) means there is a directed road from city U to city V which will give a person C gold coins. Next Q lines will contain a single integer X(1<=X<=N)

For 40 points: 1 <= N , M, Q<= 10000

For 100 points: 1 <= N , M, Q<= 100000

Output

For each query output a single line containing the number of gold coin John Snow can collect if he start his journey from city X.

Sample

InputOutput
6 6 6
1 2 10
2 3 12
3 2 13
3 4 15
3 5 2
5 6 3
1
2
3
4
5
6
25
15
15
0
3
0

Discussion

Statistics


95% Solution Ratio

NirjhorEarliest, Oct '19

anonyo.akandFastest, 0.0s

Burn_FireblazeLightest, 16 MB

Tareq_AbrarShortest, 1220B

Submit

Login to submit

Editorial

Lets build DAG using algorithm of finding SCC. Give a number to mark each SCC. Now reverse all the e...