1974984_tle.c

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

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

int N;
long M, E;
__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;
}

void relax(long u, long v, __int64 w)
{
	long i;
	__int64 min;

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

void dijkstra()
{
	long i, m;
	
	for(i = 0; i < MAX; 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;
	long u, v;
	__int64 w;

	scanf("%d%ld%ld",&N,&M,&E);
	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;
	}
	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;
}
/*
11 809 85559
56838 78279 69479
47435 60355 35158
8458 56519 108076  <----- 2
35688 85559 123709 <----- 2  <--| 
53838 78571 51802               |
19693 47581 53617  <----- 2     |
809 43292 135329   <----- 1  <--|
41276 69260 52963  <----- 2 
49179 62548 32654  
18232 43989 74417  <----- 2
54414 71527 39725

ans = 259038;
*/