2011-06-21 11:46:39Morris
b060. 5. 快遞服務
b060. 5. 快遞服務
內容 ：
「收的快」快遞公司成立之後，已經分別與市內許多中小企業公司簽訂郵件收送服務契約。由於有些公司是在同一棟大樓內，所以「收的快」需要收件的地點（收件
點）最多只有m點 (1, 2, …, m)，因此「收的快」僅先行採購了三輛貨車並聘用了三名司機，每天早上分別從收件地點 「1」, 「2」 及
「3」出發。而在與客戶的服務契約中有明訂「收的快」必須在客戶提出郵件寄送要求的隔天派人至該公司（地點）收件。為了能更有效率的服務客戶並節省收件時
間，該公司設立了收件服務登記網站，客戶如有郵件需要寄送，必須在需要收件的前一天就先上網登記。因此「收的快」就可以利用晚上先行安排三位司機隔天的收
件路線。每位司機至各地點收件的順序應與各公司上網登記的順序相符且必須能在最省油的情況下完成當天所有的收件服務。因此每位司機有可能需要在不同時間重
複到同一地點收件，或不同的司機有可能需在不同的時間點前往同一地點收件。如下面範例二(收件公司地點依序為： 4 2 4 1 5 4 3 2
1)所示，雖然司機一一開始就已經在收件地點「1」了，但是他卻不能先把後面第四個登記的公司（地點「1」）郵件先收了再前往第一、第二、或第三個登記收
件地點（地點「4」,「2」,「4」）收件。但是如果前三個登記收件的服務是由司機二或三來負責，則司機一就可以在地點「1」收了第四個登記的郵件後再前
往後面所登記的地點收件。此外，在某些情況下，不一定每輛車都要收到貨，也就是說，最佳收件方式也有可能是只需出動一或兩輛車去收貨。請寫一個程式來幫
「收的快」公司計算每天依預約順序至各收件地點收件的最少總耗油量。
輸入說明
：
輸入檔案第一行有一個整數 m，3 ≤ m ≤
200，代表「收的快」公司收件的地點數，以1至m之間的整數代號來表示每個地點。接下來的m行（第2到第m+1行），每行有m個整數，代表一個矩陣
D。第 i+1行的第j個整數是D(i, j)，D(i, j)
代表司機開車從收件點i到收件點j所需耗油量。最後有一行數串，數串之數字依序為前一天上網登記要求收件的公司地點代號，最多會有1000個收件請求。輸
入檔案中任兩個相鄰的整數都以一個空白隔開。
注意：油量矩陣D滿足三角不等式，也就是說 D(i, j) ≤ D(i, k) + D(k, j)，1 ≤ i, j, k ≤ m。因此，每輛車前往下一個收件地點時一定是直接前往，不必先繞道至其它地點再抵達下個收件地點。
注意：油量矩陣D滿足三角不等式，也就是說 D(i, j) ≤ D(i, k) + D(k, j)，1 ≤ i, j, k ≤ m。因此，每輛車前往下一個收件地點時一定是直接前往，不必先繞道至其它地點再抵達下個收件地點。
輸出說明
：
請輸出一個整數，代表收件所需最少總耗油量。
範例輸出說明:
第一組、到每個請求收件地點的司機分別為1 1 1 1 3 3 2 2 2 1，因此司機1只需從起始點1移動到地點3，司機2只需停留在地點2，司機3從起始點3移動到地點4。
第二組、到每個請求收件地點的司機分別為1 2 1 2 2 1 3 1 3，因此司機1只需從起始點1移動到地點4，再到地點2，司機2從起始點2移動到地點1，再到地點5，司機3只需從起始點3移動到地點1。
範例輸入 ：
4 0 5 0 6 6 0 5 6 1 6 0 6 1 1 1 0 1 1 1 1 4 4 2 2 2 3 5 0 1 1 1 1 1 0 2 2 2 1 1 0 2 1 2 1 3 0 1 3 2 3 4 0 4 2 4 1 5 4 3 2 1
範例輸出 ：
6 5
提示
：
出處
：
95全國資訊學科能力決賽
作法 : DP
DP[i][j] 表示其中兩輛所在的位置分別在 i, j，另外一輛在前一個指定位置k
我們必然可以知道i, j, k 轉移到下一個指定位置 l
只會有三種可能 i -> l or j -> l or k -> l
會形成三種新的狀態，新的狀態，只會由最小值來替代
作法 : DP
DP[i][j] 表示其中兩輛所在的位置分別在 i, j，另外一輛在前一個指定位置k
我們必然可以知道i, j, k 轉移到下一個指定位置 l
只會有三種可能 i -> l or j -> l or k -> l
會形成三種新的狀態，新的狀態，只會由最小值來替代
/**********************************************************************************/
/* Problem: b060 "5. 快遞服務" from 95全國資訊學科能力決賽 */
/* Language: C */
/* Result: AC (532ms, 924KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 10:39:48 */
/**********************************************************************************/
#include<stdio.h>
#define Maxv 1000000
int A[1001], Map[201][201];
int DP[201][201], Next[201][201];
void Update(int i, int j, int temp) {
int t;
if(i > j) t = i, i = j, j = t;
Next[i][j] = (Next[i][j] < temp) ? Next[i][j] : temp;
}
int DPstart(int n, int m) {
int a, b, c, num = 3;
int reduce_Map[201][201], Used[201] = {0,1,2,3};
int NewA[1001] = {3}, reduce[1001], Newnode[201] = {0,1,2,3};
for(a = 1; a <= m; a++) {
if(Used[A[a]] == 0) {
Used[A[a]] = ++num, NewA[a] = num;
Newnode[num] = A[a];
}
else NewA[a] = Used[A[a]];
reduce[a] = num;
}
for(a = 1; a <= n; a++) {
for(b = 1; b <= n; b++) {
reduce_Map[a][b] = Map[Newnode[a]][Newnode[b]];
}
}
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
DP[a][b] = Maxv;
DP[1][2] = 0, A[0] = 3;
for(a = 1; a <= m; a++) {
if(NewA[a] == NewA[a-1]) continue;
n = reduce[a];
for(b = 1; b <= n; b++)/*init*/
for(c = b+1; c <= n; c++)
Next[b][c] = Maxv;
for(b = 1; b <= n; b++)
for(c = b+1; c <= n; c++) {
if(DP[b][c] != Maxv) {
Update(b, c, DP[b][c] + reduce_Map[NewA[a-1]][NewA[a]]);
Update(NewA[a-1], b, DP[b][c] + reduce_Map[c][NewA[a]]);
Update(NewA[a-1], c, DP[b][c] + reduce_Map[b][NewA[a]]);
}
}
for(b = 1; b <= n; b++)
for(c = b+1; c <= n; c++)
DP[b][c] = Next[b][c];
}
int Min = Maxv;
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
Min = (Min < DP[a][b]) ? Min : DP[a][b];
return Min;
}
main() {
int n, m, a, b, x;
char c;
while(scanf("%d", &n) == 1) {
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++)
scanf("%d", &Map[a][b]);
m = 0;
while(scanf("%d%c", &x, &c) == 2 && c != '\n') {
A[++m] = x;
}
A[++m] = x;
printf("%d\n", DPstart(n, m));
}
return 0;
}
/**********************************************************************************/
/* Problem: b060 "5. 快遞服務" from 95全國資訊學科能力決賽 */
/* Language: C */
/* Result: AC (656ms, 760KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 00:20:41 */
/**********************************************************************************/
#include<stdio.h>
#define Maxv 1000000
int A[1001], Map[201][201];
int DP[201][201], Next[201][201];
void Update(int i, int j, int temp) {
int t;
if(i > j) t = i, i = j, j = t;
Next[i][j] = (Next[i][j] < temp) ? Next[i][j] : temp;
}
int DPstart(int n, int m) {
int a, b, c;
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
DP[a][b] = Maxv;
DP[1][2] = 0, A[0] = 3;
for(a = 1; a <= m; a++) {
if(A[a] == A[a-1]) continue;
for(b = 1; b <= n; b++)/*init*/
for(c = b+1; c <= n; c++)
Next[b][c] = Maxv;
for(b = 1; b <= n; b++)
for(c = b+1; c <= n; c++) {
if(DP[b][c] != Maxv) {
Update(b, c, DP[b][c] + Map[A[a-1]][A[a]]);
Update(A[a-1], b, DP[b][c] + Map[c][A[a]]);
Update(A[a-1], c, DP[b][c] + Map[b][A[a]]);
}
}
for(b = 1; b <= n; b++)
for(c = b+1; c <= n; c++)
DP[b][c] = Next[b][c];
}
int Min = Maxv;
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
Min = (Min < DP[a][b]) ? Min : DP[a][b];
return Min;
}
main() {
int n, m, a, b, x;
char c;
while(scanf("%d", &n) == 1) {
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++)
scanf("%d", &Map[a][b]);
m = 0;
while(scanf("%d%c", &x, &c) == 2 && c != '\n') {
A[++m] = x;
}
A[++m] = x;
printf("%d\n", DPstart(n, m));
}
return 0;
}