TRAFFICN - Traffic Network


{assign var="code" value="TRAFFICN"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Mạng lưới giao thông thành phố gồm n nút được đánh số từ 1 đến n và m đường một chiều nối các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s và t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng.

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa s và t là nhỏ nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa năm số nguyên dương n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) cách nhau bởi dấu trống. Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên dương di, ci, li cách nhau bởi dấu trống, trong đó li là độ dài ( 0< li ≤ 1000) của đường một chiều thứ i từ nút di đến nút ci. Dòng thứ j trong k dòng tiếp theo chứa ba số nguyên dương uj, vj và qj (qj ≤ 1000) cách nhau bởi dấu trống, trong đó qj là độ dài của đường hai chiều được đề xuất thứ j nối giữa hai nút uj và vj.

Dữ liệu ra

Với mỗi bộ dữ liệu, ghi ra trên một dòng độ dài nhỏ nhất có thể của đường đi ngắn nhất giữa hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t, ghi -1.

Dữ liệu vào
1
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25	

Dữ liệu ra
35

{/literal}{elseif ($par=="en" || $par=="")}{literal}

The city traffic network consists of n nodes numbered from 1 to n and m one-way roads connecting pairs of nodes. In order to reduce the length of the shortest path between two different critical nodes s and t, a list of k two-way roads are proposed as candidates to be constructed. Your task is to write a program to choose one two-way road from the proposed list in order to minimize the resulting shortest path between s and t.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains five positive integers n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) separated by space. The ith line of the following m lines contains three integers di, ci, li separated by space, representing the length li ( 0< li ≤ 1000) of the ith one-way road connecting node di to ci. The jth line of the next k lines contains three positive integers uj, vj and qj (qj ≤ 1000) separated by space, representing the jth proposed two-way road of length qj connecting node uj to vj.

Output

For each data set, write on one line the smallest possible length of the shortest path after building the chosen one two-way road from the proposed list. In case, there does not exist a path from s to t, write -1.

Example

Sample Input
1
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25	

Sample Output
35

{/literal} {/if}


hide comments
peeyush taneja: 2015-07-26 22:01:44

Finally AC

Dhruv Mullick: 2015-05-29 16:40:52

The question should rather read "write a program to choose at most one two-way road".

KESHAV BANSAL: 2015-01-31 07:58:17

tle while using scanf
WA if using INT_MAX
Finally AC by reading Comments :P
use fast i/o and use 1061109567 instead of INT_MAX

AlcatraZ: 2015-01-22 20:42:18

For my algo, INT_MAX is working fine ..But if you are adding anything to INT_MAX you will get an integer overflow..

Last edit: 2015-01-25 22:14:55
Pranav Vaish: 2014-12-10 23:54:03

Very tight time constraints. Had to optimize a lot!. Please increase the time to 2 seconds at least.

ABHISHEK004: 2014-10-24 18:47:33

@Archit Jain
don't understand why wrong answer using INT_MAX, but accepted using INF as 1061109567

___Durgesh___: 2014-09-24 12:29:01

whts wrong wid cin & cout getting tle &
got accepted using fast input
huge memory difference :P:P with previous one(tle) .. anyone please explain my doubt ..m not getting !!

Last edit: 2014-09-24 12:30:32
||N0VICE||: 2014-08-12 19:52:59

finally accepted after tonnes of WAs

Dario Sindicic: 2014-08-02 15:16:15

200th learn new dijkstra

Archit Jain: 2014-07-21 22:38:43

assign INF as 1061109567 then AC
else if u are using INT_MAX then wa

Last edit: 2014-07-21 22:38:57

Added by:Jimmy
Date:2009-01-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Regional, HCMC 2008 Tic Tac Toe