這個題我參考了別人的解題報告，題目很容易讓人產生誤解，其實不用去求最短路，求了反而不對，
直接用輸入中所給的兩點間的距離就行了。方法是三維DP。f[a][b][c]表示當前離起點最遠的車處在
c位置，另外兩車分別處在a,b位置時的所需要的最少的投遞時間。那么下一個狀態只有三種可能，即
f[a][b][c+1],即c車到了c+1處
f[a][c][c+1],即b車到了c+1處
f[b][c][c+1],即a車到了c+1處
當c==(目標點時) 結束。
采取記憶化搜索的方式。
Source Code
| Problem: 1695 |
|
User: lovecanon |
| Memory: 324K |
|
Time: 0MS |
| Language: C |
|
Result: Accepted |
-
Source Code
#include<stdio.h>
#include<string.h>
int map[31][31];
int ans[31][31][31];
int n;
int GetMin(int a,int b,int c)
{
int tmp=a<=b?a:b;
tmp=tmp<=c?tmp:c;
return tmp;
}
int solve(int a,int b,int c)
{
if(c==n) return 0;
if(ans[a][b][c+1]==0) ans[a][b][c+1]=solve(a,b,c+1);
if(ans[a][c][c+1]==0) ans[a][c][c+1]=solve(a,c,c+1);
if(ans[b][c][c+1]==0) ans[b][c][c+1]=solve(b,c,c+1);
return GetMin(ans[a][b][c+1]+map[c][c+1],ans[a][c][c+1]+map[b][c+1],ans[b][c][c+1]+map[a][c+1]);
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--)
{
int i;
scanf("%d",&n);
memset(ans,0,sizeof(ans));
for(i=1;i<=n-1;i++)
{
int j;
for(j=i+1;j<=n;j++)
{
scanf("%d",&map[i][j]);
map[j][i]=map[i][j];
}
}
printf("%d\n",solve(1,1,1));
}
return 0;
}