1974992_tle.c

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXE 20001
# define MAX 86410
# define INF 21000000000000

int N;
long M, E;
long mark[MAX];
long p[MAXE];
__int64 dis[MAX];
struct node
{
	long u;//起点
	long v;//终点
	__int64 w;//权
}Edge[MAXE];

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;
	if(aa->u==bb->u)
		return aa->v-bb->v;
	else
		return aa->u-bb->u;
}

int cmp1(const void *a, const void *b)
{
	return *(long *)a-*(long *)b;
}
void relax(long u, long v, __int64 w)
{
	long i;
	__int64 min;

	min = dis[v];
	for(i = mark[u]; i < mark[v]; i++)
		if(min>dis[p[i]]+w)
			min = dis[p[i]]+w;
	dis[v] = min;
}

void dijkstra()
{
	long i, m;
	
	for(i = M; i < E+2; i++)
		dis[i] = INF;
	dis[Edge[0].u] = m = 0;
	while(m<N)
	{
		relax(Edge[m].u,Edge[m].v,Edge[m].w);
		m++;
	}
}

void input()
{
	int i, j;
	long u, v;
	__int64 w;

	scanf("%d%ld%ld",&N,&M,&E);
	j = 0;
	memset(mark,0,sizeof(mark));
	for(i = 0; i < N; i++)
	{
		scanf("%ld%ld%I64d",&u,&v,&w);
		Edge[i].u=u;Edge[i].v=v+1,Edge[i].w=w;
		if(mark[u]==0)
		{
			p[j++] = u;
			mark[u] = 1;
		}
		if(mark[v+1]==0)
		{
			p[j++] = v+1;
			mark[u] = 1;
		}
	}
	qsort(p,j,sizeof(p[0]),cmp1);
	for(i = 0; i < j; i++)
		mark[p[i]] = i;
	qsort(Edge,N,sizeof(Edge[0]),cmp);
	dijkstra();
	if(dis[E+1]==INF)
		printf("-1\n");
	else
		printf("%I64d\n",dis[E+1]);
}

int main()
{
	input();
	return 1;
}