站外题求助
  • 板块题目总版
  • 楼主wst000
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/4 19:25
  • 上次更新2024/10/4 21:16:26
查看原帖
站外题求助
1288198
wst000楼主2024/10/4 19:25

不知道为什么超时了一个点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef const ll cll;
typedef pair<ll, ll>pll;
#define pb push_back
#define st first
#define nd second
cll llmi = -9187201950435737472;
cll llma = 9187201950435737471;
int dp[205][205][1005];
int a[205][205], n, m, b[1005], ans = 1e9;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);
	for (int i = 1; i <= m; i++)
		scanf("%d", &b[i]);
	memset(dp, 63, sizeof(dp));
	b[0] = 3, dp[2][1][0] = 0;
	for (int k = 0; k < m; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <i; j++)
			{
                if(dp[i][j][k]==1061109567)continue;
				ll ma=max(b[k],j),mi=min(b[k],j);
				if(ma!=b[k+1]&&mi!=b[k+1])
					dp[ma][mi][k + 1] = min(dp[ma][mi][k + 1]
					,dp[i][j][k] + a[i][b[k + 1]]);
				ma=max(b[k],i),mi=min(b[k],i);
				if(ma!=b[k+1]&&mi!=b[k+1])
					dp[ma][mi][k + 1] = min(dp[ma][mi][k + 1]
					,dp[i][j][k] + a[j][b[k + 1]]);
				ma=i,mi=j;
				if(ma!=b[k+1]&&mi!=b[k+1])
					dp[ma][mi][k + 1] = min(dp[ma][mi][k + 1]
					,dp[i][j][k] + a[b[k]][b[k + 1]]);
			}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
		{
			if(i==b[m]||j==b[m])continue;
			ans = min(ans, dp[i][j][m]);
		}
	printf("%d", ans);
	return 0;
}
2024/10/4 19:25
加载中...