题目地址:http://codeforces.com/problemset/problem/301/B
这个题目的意思是有n个station
你从第1个开始要到第n个去
其中从i到j的时间消耗是两个station之间的曼哈顿距离*d
还有一个特性就是如果你是第一次访问那个station的话,你所消耗的时间是可以减去ai的(2<=i<n)
然后要你求出从1到n的最短时间
我们设dp[i][j]为从i到j的时间,且下一次从j出发,那么
dp[i][j] = (abs(x[i]-x[j])+abs(y[i]-y[j]))*d-a[j]
如果是这样的话我们就要保证每次作为中转的station最多只会去一次
则dp[i][j] = min(dp[i][k]+dp[k][j]) 1<=k<=n 且k在每次循环里面只出现一次,不重复
因为在初始化dp的时候,我们减去了一个a[j],这个只有在上述情况下才满足
下面上代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100+10; int dp[maxn][maxn]; int a[maxn]; int n,d; int x[maxn],y[maxn]; int main() { while(~scanf("%d%d",&n,&d)) { for(int i=2;i<n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); a[1]=a[n]=0; for(int i=1;i<=n;i++) { dp[i][i]=0; for(int j=i+1;j<=n;j++) { dp[i][j]=dp[j][i]=abs(x[j]-x[i])+abs(y[j]-y[i]); dp[i][j]=dp[i][j]*d-a[j]; dp[j][i]=dp[j][i]*d-a[i]; //printf("i,j %d %d %d\n",i,j,dp[i][j]); } } for(int k=1;k<=n;k++)//这里的中转站枚举很关键,因为题目说了最多只能去一次 { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(dp[i][k]+dp[k][j]<dp[i][j] && i!=j && j!=k && i!=k) dp[i][j]=dp[i][k]+dp[k][j]; } //printf("i,j %d %d %d\n",i,j,dp[i][j]); } } printf("%d\n",dp[1][n]); } return 0; }