GPS Navigation become more and more important as many driver can't drive without it.
There's a small country called BEE's COLORFUL. There're many city in this country and no road but only highways in this country, i.e. no traffic lights. So it's easy to estimate the time from a city to another neighbor city.
The GPS company just make a contrast with the local radio station. The radio station will give highway reportings to GPS company, and GPS company can estimate the updated time from source to destination.
Now given the initial estimated time of each highway that connect cities (as a matrix). Your job is to calculate the initial time needed to drive from source to destination. And update your estimation when receive each highway reporting.
The number of cities is start with 0.
There are multiple test cases, each test case start with a number n (2<=n<=1000), n=0 indicates the end of input. And followed by two integer s and t, the source and destination city. Followed by a n by n matrix. The values in matrix are the estimated time between cities, and -1 if the highway is blocked. And followed by a number e, the number of highway reportings, followed by e lines, each line contains 3 integer x, y and w, x and y are the number of city and w is the updated estimated time.
Foreach test case, first output the initial estimated time from source city to destination city in a line. Than for each highway reporting, output the updated estamated time in a line.
2 0 1 0 860 -1 0 1 0 1 901 0
860 901
Migrated from old NTUJ.
DE
| No. | Testdata Range | Score |
|---|