我判断负环是这样子写的,请问那里的问题
num[t] = num[dian] + 1;
if (num[t] > n/**/)//因为加了0号节点,所以有n + 1个点
{
return false;
}
const int N = 5e3 + 5;
const int M = 5e3 + 5;
int head[N];
int cnt;
int vis[N];
int dis[N];
int num[N];
int n, m;
struct EDGE
{
int v;
int w;
int next;
}EDGE[M + N];
void add(int u, int v, int w)
{
cnt++;
EDGE[cnt].v = v;
EDGE[cnt].w = w;
EDGE[cnt].next = head[u];
head[u] = cnt;
}
bool SPFA(int s)
{
queue<int>que;
memset(dis, 0x3f3f3f, sizeof(dis));
dis[s] = 0;
//memset(vis, 0, sizeof(vis));
que.push(s);
vis[s] = 1;
num[s]++;
while (!que.empty())
{
int dian = que.front();
que.pop();
vis[dian] = 0;
for (int i = head[dian]; i; i = EDGE[i].next)
{
int t = EDGE[i].v;
int w = EDGE[i].w;
if (dis[t] > dis[dian] + w)
{
dis[t] = dis[dian] + w;
num[t] = num[dian] + 1;
if (num[t] > n/**/)
{
return false;
}
if (vis[t] != 1)
{
vis[t] = 1;
que.push(t);
}
}
}
}
return true;
}
void solve()
{
cin >> n >> m;
int u, v, c;
while (m--)
{
cin >> v >> u >> c;
add(u, v, c);
}
for (int i = 1; i <= n; i++)
add(0, i, 0);
if (SPFA(0))
{
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
}
else
{
cout << "NO" << endl;
}
}
int main()
{
solve();
return 0;
}