a342:
交通費用
Content
有一個城市, 其道路網絡剛剛好形成一個 N x N 的格子矩陣。該城市有個非常嚴格的自動路段使用收費系統。 每經過一段路段 (由一個路口至第二個路口為之一段路段) 均要收費, 而且每段路的收費各有不同。 若一行程中使用同一路段多次, 則每次使用均需收同樣的費用。 該城市還有一個十分奇特的路段使用規定, 就是在每一個路口都必須左轉或右轉而不可以直行。
小明住在堿市的西北端的路口 (下圖的左上角位置) 要到位於城市的東南端路口 (圖的右下角位置) 的一間學校參加信息學奧林匹克競賽。 你的任務就是要為小明找出最少需要付多少路段使用費才可到達競賽現場。
Input
輸入資料的第一行含有一個正整數 N, 它代表格子矩陣的大小。 換言之它代表該城市共有 N+1 條南北向及 N+1 條東西向的道路。 2 ≤ N ≤ 400
隨後有 2N+1 行, 在這 2N+1 行的第 1, 3, 5, ... 2N+1 行上有 N 個正整數, 它們表示由西向東 (由左至右) 每段東西向的路段的收費。 而在第 2, 4, 6, ..., 2N 行上, 每行則有 N+1 個正整數, 它們表示著由西向東 (由左至右) 每段南北向路段的數費。 每段路的費用均在 1 至 2000 之間。
Output
輸出應只有一個正整數, 它代表你找到的最少道路使用費用。
Sample Input
#1
3 1 7 6 9 2 3 8 5 20 10 3 16 2 5 1 9 1 7 1 2 3 12 3 6
Sample Output
#1
22
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (9%): 1.0s , <1K
公開 測資點#1 (9%): 1.0s , <1K
公開 測資點#2 (9%): 1.0s , <1K
公開 測資點#3 (9%): 1.0s , <1K
公開 測資點#4 (9%): 1.0s , <1M
公開 測資點#5 (9%): 1.0s , <1M
公開 測資點#6 (9%): 1.0s , <1M
公開 測資點#7 (9%): 1.0s , <1M
公開 測資點#8 (9%): 1.0s , <1M
公開 測資點#9 (9%): 1.0s , <1M
公開 測資點#10 (10%): 1.0s , <10M
公開 測資點#0 (9%): 1.0s , <1K
公開 測資點#1 (9%): 1.0s , <1K
公開 測資點#2 (9%): 1.0s , <1K
公開 測資點#3 (9%): 1.0s , <1K
公開 測資點#4 (9%): 1.0s , <1M
公開 測資點#5 (9%): 1.0s , <1M
公開 測資點#6 (9%): 1.0s , <1M
公開 測資點#7 (9%): 1.0s , <1M
公開 測資點#8 (9%): 1.0s , <1M
公開 測資點#9 (9%): 1.0s , <1M
公開 測資點#10 (10%): 1.0s , <10M
Hint ：
上例是對應下圖。小明所行經的路段以紅色標示了出來, 其總路費是 22。
Tags:
出處:
[管理者：
ricky
(電腦黃)
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||