int dis[N];
bool flag[N];
这俩定义在方法里面,存在栈中 答案错误。
定义在全局变量中,AC。
并且已经初始化过了。
很怪。
结论就是在acwing刷题 都用全局变量 不用局部变量。
下面这个WA
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int MY_MAX = 0x3f3f3f3f;
const int N = 510;
int g[N][N];
void add(int a, int b, int c) {
if (g[a][b] > c) {
g[a][b] = c;
}
}
int main()
{
int n, m;
cin >> n >> m;
int dis[N];
bool flag[N];
// 初始化dijkstra数据结构: dis数组与标记集合
for (int i = 1; i <= n; i ++) { dis[i] = MY_MAX; flag[N] = false;}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
g[i][j] = MY_MAX;
}
}
// 初始化邻接矩阵
for (int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dis[1] = 0;
for (int i = 1; i <= n; i ++) {
// 找到flag=false的集合中 dis值最小的节点u
int u = -1;
for (int j = 1; j <= n; j ++) {
if (!flag[j] && ( u == -1 || dis[u] > dis[j])) {
u = j;
}
}
// cout << u << endl;
if (u == -1) {
break;
}
// 标记u
flag[u] = true;
// 以u为中转节点 修改u的邻接点
for (int j = 1; j <= n; j ++) {
if (g[u][j] != MY_MAX && dis[j] > dis[u] + g[u][j]) {
dis[j] = dis[u] + g[u][j];
}
}
}
cout << (dis[n] == MY_MAX ? -1 : dis[n]);
}
下面这个ac。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int MY_MAX = 0x3f3f3f3f;
const int N = 510;
int g[N][N];
int dis[N];
bool flag[N];
void add(int a, int b, int c) {
if (g[a][b] > c) {
g[a][b] = c;
}
}
int main()
{
int n, m;
cin >> n >> m;
// 初始化dijkstra数据结构: dis数组与标记集合
for (int i = 1; i <= n; i ++) { dis[i] = MY_MAX; flag[N] = false;}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
g[i][j] = MY_MAX;
}
}
// 初始化邻接矩阵
for (int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dis[1] = 0;
for (int i = 1; i <= n; i ++) {
// 找到flag=false的集合中 dis值最小的节点u
int u = -1;
for (int j = 1; j <= n; j ++) {
if (!flag[j] && ( u == -1 || dis[u] > dis[j])) {
u = j;
}
}
// cout << u << endl;
if (u == -1) {
break;
}
// 标记u
flag[u] = true;
// 以u为中转节点 修改u的邻接点
for (int j = 1; j <= n; j ++) {
if (g[u][j] != MY_MAX && dis[j] > dis[u] + g[u][j]) {
dis[j] = dis[u] + g[u][j];
}
}
}
cout << (dis[n] == MY_MAX ? -1 : dis[n]);
}
很怪