与样例有出入+满江紫
查看原帖
与样例有出入+满江紫
724966
YiBoRrui6楼主2023/5/20 16:37

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;
}

2023/5/20 16:37
加载中...