2021.08.24【NOIP提高A、B组】模拟 Mobile Service

思路：

设f[i][x][y]表示前i-1个完成，有两个位置在x和y上

转移就是从上一个位置转移过来

c o d e code code

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n, l;
int a[10010], h[1010][1010];
int f[3][1010][1010];

int main()
{
	scanf("%d%d", &l, &n);
	for(int i=1; i<=l; i++)
		for(int j=1; j<=l; j++)
			scanf("%d", &h[i][j]);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	memset(f, 0x3f, sizeof(f));
	f[0][1][2]=0;
	a[0]=3;
	int ans=1e9;
	for(int i=1; i<=n; i++)
	{
		memset(f[i&1], 0x3f, sizeof(f[i&1]));
		for(int x=1; x<=l; x++)
			for(int y=1; y<=l; y++)
			{
				if(x!=y&&x!=a[i-1]&&y!=a[i-1])
				{
					if(i&1)
					{
						f[1][a[i-1]][y]=min(f[1][a[i-1]][y], f[0][x][y]+h[x][a[i]]);
						f[1][x][a[i-1]]=min(f[1][x][a[i-1]], f[0][x][y]+h[y][a[i]]);
						f[1][x][y]=min(f[1][x][y], f[0][x][y]+h[a[i-1]][a[i]]);
					}
					else
					{
						f[0][a[i-1]][y]=min(f[0][a[i-1]][y], f[1][x][y]+h[x][a[i]]);
						f[0][x][a[i-1]]=min(f[0][x][a[i-1]], f[1][x][y]+h[y][a[i]]);
						f[0][x][y]=min(f[0][x][y], f[1][x][y]+h[a[i-1]][a[i]]);
					}
				}
			}
		if(i==n)
		{
			for(int x=1; x<=l; x++)
				for(int y=1; y<=l; y++)
					ans=min(ans, f[i&1][x][y]);
		}
	}
	printf("%d", ans);
	return 0;
}