Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
TRAFFICN  Traffic Network 
The city traffic network consists of n nodes numbered from 1 to n and m oneway 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 twoway roads are proposed as candidates to be constructed. Your task is to write a program to choose one twoway 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 oneway 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 twoway 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 twoway 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
Được gửi lên bởi:  Jimmy 
Ngày:  20090104 
Thời gian chạy:  1s 
Giới hạn mã nguồn:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Ngôn ngữ cho phép:  Tất cả ngoại trừ: ERL GOSU JSRHINO NODEJS PERL6 PYPY RUST SED VB.NET 
Nguồn bài:  ACM Regional, HCMC 2008 Tic Tac Toe 
hide comments


20210527 18:04:02
Tham khảo: https://vnspoj.github.io/problems/TRAFFICN 

20210324 16:33:39
ez 

20200725 06:22:33
Thk cmt ngay dưới bị điên 

20200725 06:20:59
nhật hào bẩn 

20200503 09:41:07
xin gợi ý ạ. Em mới học ijk 

20200311 18:57:20
AC nhé thằng _spontaneously_ 

20200311 17:53:16
_spontaneously_ Trâu đéo AC bọn l 

20190923 05:03:58
13 đấm mới AC :<. Đừng lưu LLONG_MAX bị WA á 

20190801 11:36:42
trau AC 

20190729 10:51:09
Last edit: 20190729 11:46:35 