CodeForces Round #119 (187B) - AlgoRace

 這道題我想啦好久~~只想出了dp[60][60][60][1000]這種完全沒效率的DP(更新的時候也要掃描60^3的空間...so..效率是1000*60^6..囧...)...是看了別人的代碼才恍然大悟的...做1000次Floyd即可~~效率1000*60^3=216000000勉強能接受..囧...

Program：
[cpp]
#include<iostream> 
#include<algorithm> 
#include<stdio.h> 
#include<string.h> 
#include<cmath> 
#include<queue> 
#define oo 2000000000 
#define ll long long 
using namespace std;  
int n,m,r,car[63][63][63],ans[63][63][1003]; 
void getanswer() 
{ 
       int i,j,t,k;  
       for (i=1;i<=n;i++) 
          for (j=1;j<=n;j++) 
          { 
               ans[i][j][0]=1000000; 
               for (k=1;k<=m;k++) 
                  if (ans[i][j][0]>car[k][i][j]) ans[i][j][0]=car[k][i][j]; 
          } 
       for (t=1;t<=1000;t++) 
       { 
             for (i=1;i<=n;i++) 
               for (j=1;j<=n;j++) 
                  ans[i][j][t]=ans[i][j][t-1]; 
             for (k=1;k<=n;k++) 
                for (j=1;j<=n;j++) 
                   for (i=1;i<=n;i++) 
                      if (ans[i][j][t]>ans[i][k][t-1]+ans[k][j][0]) 
                          ans[i][j][t]=ans[i][k][t-1]+ans[k][j][0]; 
       } 
} 
int main() 
{        
       scanf("%d%d%d",&n,&m,&r); 
       int i,j,x,y,k,s,e,t; 
       for (t=1;t<=m;t++) 
       { 
             for (i=1;i<=n;i++) 
                for (j=1;j<=n;j++) 
                   scanf("%d",&car[t][i][j]); 
             for (k=1;k<=n;k++) 
                for (i=1;i<=n;i++) 
                   for (j=1;j<=n;j++) 
                      if (car[t][i][j]>car[t][i][k]+car[t][k][j]) 
                          car[t][i][j]=car[t][i][k]+car[t][k][j]; 
       }  
       getanswer(); 
       while (r--) 
       { 
             scanf("%d%d%d",&s,&e,&t);  
             printf("%d\n",ans[s][e][t]); 
       } 
       return 0; 
}