infinity

這個題我參考了別人的解題報告，題目很容易讓人產生誤解，其實不用去求最短路，求了反而不對，
直接用輸入中所給的兩點間的距離就行了。方法是三維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

• 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;
      }