C++14(g++5.4) 解法, 执行用时: 229ms, 内存消耗: 165828K, 提交时间: 2020-09-01 19:34:48
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=205,M=1005;
const int INF=1061109567;
int n,m;
int c[N][N];
int dp[M][N][N];
int a[M];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
memset(dp,63,sizeof(dp));
dp[0][1][2]=0;
a[0]=3;
for(int i=0;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(j!=a[i]&&k!=a[i]&&j!=k)
{
dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+c[a[i]][a[i+1]]);
dp[i+1][a[i]][k]=min(dp[i+1][a[i]][k],dp[i][j][k]+c[j][a[i+1]]);
dp[i+1][j][a[i]]=min(dp[i+1][j][a[i]],dp[i][j][k]+c[k][a[i+1]]);
}
int ans=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) ans=min(ans,dp[m][i][j]);
printf("%d",ans);
return 0;
}
C++ 解法, 执行用时: 260ms, 内存消耗: 174864K, 提交时间: 2022-07-12 11:26:34
#include<bits/stdc++.h>
using namespace std;
const int N=210,M=1010,inf=0x3f3f3f3f;
int n,m;
int w[N][N];
int f[M][N][N];
int a[M];
int main()
{ cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
a[0]=3;
memset(f,100,sizeof(f));
f[0][1][2]=0;
for(int i=0;i<m;i++)
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++)
{ int z=a[i];
if(x==y||y==z||x==z) continue;
int u=a[i+1];
f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+w[z][u]);
f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+w[y][u]);
f[i+1][z][y]=min(f[i+1][z][y],f[i][x][y]+w[x][u]);
}
int ans=inf;
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++)
{ int z=a[m];
if(x==y||y==z||x==z) continue;
ans=min(ans,f[m][x][y]);
} cout<<ans<<endl;
return 0;
}
。公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。
，位置是1~200的整数。。L是位置数；N是请求数。每个位置从1到L编号。
下L行每行包含L个非负整数。第i+1行的第j个数表示c(i,j) ，并且它小于2000。最后一行包含N个数，是请求列表。一开始三个服务员分别在位置1，2，3。