我本题代码中,如果最后求答案的时候,将 res 的初始值设为 1e9 的话,可以获得 AC;但是如果把 res 初始为 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;
}