Bellman-ford获得10pts 测试点1至点10全部RE
各位神犇帮忙看一下有么有救qwq
#include<bits/stdc++.h>
using namespace std;
int dis[5050];
bool dict[5050], judge[5050];
int h[5050], edgecnt;
int n, m;
int inf = 9999999;
struct Edge
{
int to, w, next;
}edge[5050];
void init()
{
for (int i = 0; i <= n; i++) h[i] = -1;
for (int i = 1; i <= n; i++) dict[i] = 0;
edgecnt = 0;
}
void addedge(int u, int v, int w)
{
edge[++edgecnt].to = v;
edge[edgecnt].w = w;
edge[edgecnt].next = h[u];
h[u] = edgecnt;
}
int main()
{
scanf("%d%d", &n, &m);
init();
int uu, vv, ww;
for (int i = 1; i <= m; i++){
scanf("%d%d%d", &vv, &uu, &ww);
addedge(uu, vv, ww);
}
for (int i = 1; i <= n; i++) //超级源点
addedge(0, i, 0);
queue<int> q;
memset(dis, 63, sizeof(dis));
dis[0] = 0; dict[0] = 1;
q.push(0);
while (!q.empty())
{
int expa = q.front();
q.pop();
dict[expa] = 0;
for (int i = h[expa]; i != -1; i = edge[i].next){
if (dis[edge[i].to] > dis[expa] + edge[i].w){
dis[edge[i].to] = dis[expa] + edge[i].w;
if (!dict[edge[i].to]){
judge[edge[i].to]++;
dict[edge[i].to] = 1;
if (judge[edge[i].to] == n+1){
printf("NO");
return 0;
}
q.push(edge[i].to);
}
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}