CF301B
这不最短路的板子题吗?
思路
用 \(ak\) 代表走到第 \(k\) 点时的可恢复单位时间的值。
\(i\) 到 \(j\) 的距离是 \(\left ( \left | xi-xj \right | + \left | yi-yj \right | \right ) \times d-ak\)。
再打一下最短路代码,建议 Floyd,因为短。
AC Code
#include <bits/stdc++.h>
using namespace std;
int n,d,a[105],x[105],y[105],dis[105][105];
void floyd() {
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(dis[i][j]>dis[i][k]+dis[k][j]&&j!=k&&i!=k)
dis[i][j]=dis[i][k]+dis[k][j];
}
int main() {
cin>>n>>d;
for(int i=2; i<n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
for(int i=1; i<=n; dis[i][i]=0,i++)
for(int j=i+1; j<=n; j++)
dis[i][j]=(abs(x[j]-x[i])+abs(y[j]-y[i]))*d-a[j],dis[j][i]=(abs(x[j]-x[i])+abs(y[j]-y[i]))*d-a[i];
floyd();
cout<<dis[1][n];
return 0;
}
标签:right,left,int,题解,Yaroslav,CF301B,105,dis
From: https://www.cnblogs.com/AUBSwords/p/18117697