Posted on 2008-09-07 13:30
Hero 阅读(105)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
//1716 Accepted 880K 0MS C++ 2474B PKU
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int INF = 100000000 ;
const int size = 11000 ;
struct NODE
{
int en ;
int len ;
int next ;
};
struct NODE nhead[size*100] ;
int chead ;
int dist[size+100] ;
int visit[size+100] ;
int que[size*20] ;
int head, tail ;
int inmax ;
int inn ;
void input()
{
int sn, en ; int len = 2 ; inmax = -1 ; chead = size ;
for( int i=0; i<size; i++ ) nhead[i].next = -1 ;
for( int i=1; i<=inn; i++ )
{
scanf( "%d %d", &sn, &en ) ; sn++ ; en++ ; en++ ;
if( inmax < en ) inmax = en ;
nhead[sn].len++ ; nhead[chead].next = nhead[sn].next ; nhead[sn].next = chead ;
nhead[chead].en = en ; nhead[chead].len = -2 ; chead++ ;
}
for( int i=1; i<=inmax; i++ )
{
sn = i ; en = i-1 ;
nhead[sn].len++ ; nhead[chead].next = nhead[sn].next ; nhead[sn].next = chead ;
nhead[chead].en = en ; nhead[chead].len = 1 ; chead++ ;
sn = i-1; en = i ;
nhead[sn].len++ ; nhead[chead].next = nhead[sn].next ; nhead[sn].next = chead ;
nhead[chead].en = en ; nhead[chead].len = 0 ; chead++ ;
}
for( int i=1; i<=inmax; i++ )
{
nhead[0].len++ ; nhead[chead].next = nhead[0].next; nhead[0].next = chead ;
nhead[chead].en = i ; nhead[chead].len = 0 ; chead++ ;
}
/*
for( int i=0; i<=inmax; i++ )
{
printf( "head[%d]==%d", i, i ) ;
for( int p=nhead[i].next; p!=-1; p=nhead[p].next )
printf( " %4d ", nhead[p].en ) ;
printf( "\n" ) ;
}
*/
}
void SPFA( int sn, int n )
{
for(int i=0; i<=n; i++)
{
dist[i] = INF ; visit[i] = 0 ;
}
tail = 0 ; que[++tail] = sn ; dist[sn] = 0 ; visit[sn] = 1 ;
int cursn = 100 ;
while( tail > 0 )
{
cursn = que[tail--] ; visit[cursn] = 0 ;
for( int p=nhead[cursn].next ; p!=-1; p=nhead[p].next )
{
if( dist[nhead[p].en] > dist[cursn] + nhead[p].len )
{
dist[nhead[p].en] = dist[cursn] + nhead[p].len ;
if( 0 == visit[nhead[p].en] )
{
visit[nhead[p].en] = 1 ; que[++tail] = nhead[p].en ;
}
}
}
}
}
void process()
{
SPFA( 0, inmax ) ;
//for( int i=0; i<=inmax; i++ ) printf( "dist[%d]===%d\n", i, dist[i] ) ;
printf( "%d\n", 0-dist[inmax] ) ;
}
int main()
{
//freopen( "in.txt", "r", stdin ) ;
while( scanf( "%d", &inn ) != EOF )
{
input() ;
process() ;
//output() ;
}
return 0 ;
}