思路:最短路,map[i][j] = d*(|x[i]-x[j]| + |y[i]-y[j]|) - add[i]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
long long int map[105][105],vis[105],dist[105],add[105];
int n,d;
void init()
{
memset(vis,0,sizeof(vis));
for(int i = 0; i < 105; i ++)
{
for(int j = 0; j < 105; j ++)
{
map[i][j] = 1 << 30;
}
}
return ;
} int main()
{
int x[105],y[105];
int ans,k;
//freopen("in.c","r",stdin);
while(~scanf("%d%d",&n,&d))
{
init();
for(int i = 2; i <= n-1; i ++)
scanf("%d",&add[i]);
for(int i = 1; i <= n; i ++)
scanf("%d%d",&x[i],&y[i]);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
map[i][j] = (abs(x[i] - x[j]) +abs(y[i] - y[j]))*d - add[i];
}
// for(int i = 1;i <= n;i ++)
// {
// for(int j = 1;j <= n;j ++)
// {if(i != j) printf("%d<-->%d == %d ",i,j,map[i][j]),printf("\n");}
// }
for(int i = 1;i <= n;i ++)
dist[i] = map[1][i];
ans = 0;
vis[1] = 1;
for(int i = 1;i <= n;i ++)
{
long long int min = 1 << 30;
for(int j = 1;j <= n;j ++)
{
if(!vis[j] && min > dist[j])
{
k = j;
min = dist[j];
}
}
vis[k] = 1;
for(int j = 1;j <= n;j ++)
{
if(!vis[j] && dist[j] > map[k][j] + dist[k])
dist[j] = map[k][j] +dist[k];
}
}
printf("%d\n",dist[n]);
}
return 0;
}