这个题我参考了别人的解题报告，题目很容易让人产生误解，其实不用去求最短路，求了反而不对，
直接用输入中所给的两点间的距离就行了。方法是三维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;
}