AC了,但还有一点疑惑
查看原帖
AC了,但还有一点疑惑
775549
lml0928楼主2024/3/13 21:29

我本题代码中,如果最后求答案的时候,将 resres 的初始值设为 1e9 的话,可以获得 AC;但是如果把 resres 初始为 0x3f3f3f3f 的话,会 WA 两个点(4号和7号),大佬能帮忙看一下吗?

下面是 WA 了两个点的代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 21;
int dp[1 << N][N];
int dis[N][N];
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	memset(dp, 0x3f, sizeof dp);
	memset(dis, 0x3f, sizeof dis);
	for(int i = 1, we = 1; i <= n; i++, we <<= 1) dis[i][i] = dp[we][i] = 0;
	while(m--)
	{
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		dis[x][y] = min(dis[x][y], w);
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			for(int k = 1; k <= n; k++)
			{
				dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
			}
		}
	}
	for(int i = 0; i < (1 << n); i++)
	{
		for(int u = 1, wu = 1; u <= n; u++, wu <<= 1)
		{
			if((i & wu) == 0) continue;
			for(int v = 1, wv = 1; v <= n; v++, wv <<= 1)
			{
				if(((i & wv) != 0) || u == v) continue;
				dp[i | wv][v] = min(dp[i | wv][v], dp[i][u] + dis[u][v]);
			}
		}
	}
	int res = 0x3f3f3f3f;//如果此处和下面的if语句中都把无穷大设为 1e9,那么会AC
	for(int i = 1; i <= n; i++) res = min(res, dp[(1 << n) - 1][i]);
	if(res != 0x3f3f3f3f) printf("%d", res);
	else puts("No");
	return 0;
}
2024/3/13 21:29
加载中...