All Tracks Problem

The Great Cyrus

Flow, Greedy algorithm


View Russian Translation

The great Cyrus is in a great war with his enemies.

His country has n cities and m bidirectional roads. Cities are numbered from 1 to n. The capital is city number s and his enemies are in city t. There is no direct road between s and t.

He wants to mobilize some cities (he can't mobilize s and t). Enemies can't pass mobilized cities. He wants to do this so that enemies won't be able to get to the capital crossing only unmobilized cities and using only country roads.

For each city i which is not s and t, Cyrus knows mobilizing city i costs ai gold and bi silver coins.

Gold is way too worthier than silver in his country, so in the first place he wants to minimize the total gold coins he spends. And among all possible solutions with minimum gold, he chooses the mobilizing way with minimum total silver coins.

Your task as Cyrus' minister is to chose this optimal solution and tell him how much gold and silver coins he needs.

Please note that there may be no path from t to s and so Cyrus needs no coins at all.


The first line of input contains two integers n and m (3 ≤ n ≤ 500, 1 ≤ m ≤ n(n-1)/2 -1).

The second line contains two integers s and t (1 ≤ s, t ≤ n, s ≠ t).

The next n-2 lines, each line contains two integers ai and bi for every city except s and t, in order of cities indices (1 ≤ ai, bi ≤ 1000).

The next m lines contain the roads. Each line contains two integers v and u, endpoints of a road.

(1 ≤ v, u ≤ n, v ≠ u, there is at most 1 road between two cities and there'll be no road between s and t).


Print two integers in a line, number of gold and silver coins needed in an optimal solution.

4 3
1 4
10 30
10 40
1 2
3 2
4 3
10 30
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications