# 【Tyvj1061】Mobile Service

## 样例输入 SampleInput

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

5

Tyvj 1061

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
int f[2][1001][1001];
int a[1001][1001];
int q[1001];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
scanf("%d%d",&l,&n);
for (i=1;i<=l;i++) for (j=1;j<=l;j++) scanf("%d",&a[i][j]);
for (t=0;t<=1;t++) for (i=0;i<=l;i++) for (j=0;j<=l;j++) f[t][i][j]=inf/2711;
for (i=1;i<=n;i++) scanf("%d",&q[i]);
f[0][1][2]=0;
q[0]=3;
for (t=0;t<n;t++)
{
for (i=1;i<=l;i++) for (j=1;j<=l;j++) f[(t+1)&1][i][j]=inf;
for (i=1;i<=l;i++) for (j=1;j<=l;j++)
{
f[(t+1)&1][i][j]=min(f[(t+1)&1][i][j],f[t&1][i][j]+a[q[t]][q[t+1]]);
f[(t+1)&1][i][q[t]]=min(f[(t+1)&1][i][q[t]],f[t&1][i][j]+a[j][q[t+1]]);
f[(t+1)&1][q[t]][j]=min(f[(t+1)&1][q[t]][j],f[t&1][i][j]+a[i][q[t+1]]);
}
}
z=inf;
for (i=1;i<=l;i++) for (j=1;j<=l;j++)
{
if (f[n&1][i][j]!=0) z=min(z,f[n&1][i][j]);
}
printf("%d\n",z);
return 0;
}``````