2233371_ac_45ms_160k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# define MAXVex 1001
# define MAXE 21001
# define INF 10000000

int n, e;
struct graphnode
{
	int st;
	int ed;
	long w;
}Edge[MAXE];

long dis[MAXVex];

int Relax(int u, int v, long w)
{
	int sign;

	sign = 0;
	if(dis[u]!=INF&&dis[v]>dis[u]+w)
	{
		sign = 1;
		dis[v] = dis[u]+w;
	}
	return sign;
}

int bellman_ford()
{
	int i, j;
	int sign;

	for(i = 0; i < n; i++)
		dis[i] = INF;
	dis[0] = 0;

	sign = 1;
	for(i = 1; i < e+n-1&&sign; i++)
	{	
		sign = 0;
		for(j = 0; j < e+n-1; j++)
			if(Relax(Edge[j].st,Edge[j].ed,Edge[j].w)==1)
				sign = 1;
	}
	for(i = 0; i < e+n-1; i++)
		if(dis[Edge[i].ed]>dis[Edge[i].st]+Edge[i].w)
			return 0;
	return 1;
}

int main()
{
	int i, j, ML, MD, ans;

	scanf("%d%d%d",&n,&ML,&MD);
	e = ML+MD;
	for(j = 0; j < n - 1; j++)
	{
		Edge[j].st = j+1;
		Edge[j].ed = j;
		Edge[j].w = 0;
	}
	for(i = n-1; i < ML+n-1; i++)
	{
		scanf("%d%d%ld",&Edge[i].st,&Edge[i].ed,&Edge[i].w);
		Edge[i].st--;Edge[i].ed--;
		if(Edge[i].st==Edge[i].ed-1)
		{
			Edge[Edge[i].st].w = Edge[i].w;
			Edge[Edge[i].st].st = Edge[i].st;
			Edge[Edge[i].st].ed = Edge[i].ed;
			ML--;i--;e--;
		}
	}
	for(; i < e+n-1; i++)
	{
		scanf("%d%d%ld",&Edge[i].ed,&Edge[i].st,&Edge[i].w);
		Edge[i].w *= -1;
		Edge[i].st--;Edge[i].ed--;
	}
	ans = bellman_ford();
	if(dis[n-1]==INF)
		printf("-2\n");
	else
		if(ans == 0)
			printf("-1\n");
		else
			printf("%ld\n",dis[n-1]);
	return 1;
}