[HDU] 4725 니 아 그래프 최 단 경로

전송 문: 【 HDU 】 4725 니 아 그래프 에서 가장 짧 은 경로
제목 대의: 평면 무 방향 도, N 점, M 변 을 드 리 겠 습 니 다.각 변 에 하나의 변 권 cost 가 있 는데 이 변 에서 비용 이 들 어야 한 다 는 대 가 를 나타 낸다.또한 그림 에서 각 노드 는 하나의 등급 이 있 는데 그 중에서 등급 x 의 점 에서 등급 x + 1 또는 x - 1 의 임 의 한 점 에 도달 할 수 있 지만 C 가 필요 합 니 다.예 를 들 어 변 (u, v) 이 존재 하고 u 의 등급 과 v 의 등급 이 1 차이 가 나 면 u 에서 v 까지 소비 cost 를 선택 하여 도착 할 수도 있 고 소비 C 를 선택 하여 도착 할 수도 있다.현재 당신 의 임 무 는 1 에서 N 까지 의 비용 이 가장 적은 길 을 찾 는 것 입 니 다. 출력 비용, 무 해 출력 - 1.
제목 분석:
이 문 제 는 하나의 사상 을 사 용 했 고 비교적 통용 되 는 사상 이기 도 하 다.
영향 을 미 치 는 요 소 를 추가 로 끌 어 내 고 관계 에 따라 변 을 만든다.
본 문제 로 말하자면 각 노드 에 하나의 등급 이 있 는데 우 리 는 왜 등급 을 끌 어 내 서 추가 로 고려 하지 않 습 니까?
각 노드 u 에 대해 그의 등급 은 x 이 고 등급 x + 1 이 존재 하면 변경 (u, n + x + 1, C) 을 만 들 고 등급 x - 1 이 같은 이치 가 존재 한다.
그리고 모든 노드 u 에 대해 그의 등급 은 x 이 고 그러면 건축 변 (n + x, u, 0).
이렇게 처리 한 후에 우 리 는 문 제 를 1 번 에서 N 까지 의 최 단 로 를 구 하 는 데 성공 하면 된다.
처 리 됐 지만 건설 이 적절 하지 않 으 면 TLE.
우 리 는 자세히 관찰 한 결과 m 개의 변 이 반드시 양 방향 이 어야 하 는 것 을 제외 하고 다른 변 의 단 방향 은 충분 하 다 는 것 을 알 수 있다.그럼 남 은 변 이 많 으 면 제거 할 수 있 습 니 다.
이번에 제 가 사용 한 SPFA 는 본 문제 에 대해 최적화 또는 SPFA 의 SLF 최 적 화 를 입력 하지 않 으 면 G + TLE, C + + 600 + ms,
입력 최적화 또는 SLF 최적화 G + 500 ~ 600 + ms 추가
둘 다 추가 하면 218 ms 까지 최적화 할 수 있 습 니 다.
근 데 내 가 최적화 되 지 않 은 코드 를 끊 을 수 있어.
코드 는 다음 과 같 습 니 다:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int MAXN = 100005 ;
const int MAXQ = 200005 ;
const int MAXE = 1000005 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int v , c , n ;
	Edge () {}
	Edge ( int var , int cost , int next ) :
		v ( var ) , c ( cost ) , n ( next ) {}
} ;

Edge E[MAXE] ;
int hd[MAXN << 1] , cntE ;
int d[MAXN << 1] ;
int LV[MAXN] , vis[MAXN] ;
int Q[MAXQ] , head , tail ;
bool inq[MAXN << 1] ;
int NV , NE , C ;

void addedge ( int u , int v , int c ) {
	E[cntE] = Edge ( v , c , hd[u] ) ;
	hd[u] = cntE ++ ;
}

void read ( int &x ) {
	x = 0 ;
	char c = ' ' ;
	while ( c < '0' || c > '9' )
		c = getchar () ;
	while ( c >= '0' && c <= '9' ) {
		x = x * 10 + c - '0' ;
		c = getchar () ;
	}
}

void spfa () {
	clear ( d , INF ) ;
	clear ( inq , 0 ) ;
	head = tail = 0 ;
	d[1] = 0 ;
	Q[tail ++] = 1 ;
	while ( head != tail ) {
		int u = Q[head ++] ;
		if ( head == MAXQ )
			head = 0 ;
		inq[u] = 0 ;
		for ( int i = hd[u] ; ~i ; i = E[i].n ) {
			int v = E[i].v , val = d[u] + E[i].c ;
			if ( d[v] > val ) {
				d[v] = val ;
				if ( !inq[v] ) {
					inq[v] = 1 ;
					if ( d[v] < d[Q[head]] ) {
						Q[-- head] = v ;
						if ( head == 0 )
							head = MAXQ - 1 ;
					}
					else {
						Q[tail ++] = v ;
						if ( tail == MAXQ )
							tail = 0 ;
					}
				}
			}
		}
	}
}
	

void work () {
	int u , v , c ;

	cntE = 0 ;
	clear ( hd , -1 ) ;
	clear ( vis , 0 ) ;
	read ( NV ) , read ( NE ) , read ( C ) ;
	REPF ( i , 1 , NV ) {
		read ( LV[i] ) ;
		addedge ( NV + LV[i] , i , 0 ) ;
		vis[LV[i]] = 1 ;
	}
	REPF ( i , 1 , NV ) {
		if ( vis[LV[i] + 1] )
			addedge ( i , NV + LV[i] + 1 , C ) ;
		if ( vis[LV[i] - 1] )
			addedge ( i , NV + LV[i] - 1 , C ) ;
	}
	REP ( i , NE ) {
		read ( u ) , read ( v ) , read ( c ) ;
		addedge ( u , v , c ) ;
		addedge ( v , u , c ) ;
	}
	spfa () ;
	if ( d[NV] == INF )
		printf ( "-1
" ) ;
	else
		printf ( "%d
" , d[NV] ) ;
}
			
int main () {
	int T , cas ;
	for ( read ( T ) , cas = 1 ; cas <= T ; ++ cas ) {
		printf ( "Case #%d: " , cas ) ;
		work () ;
	}
	return 0 ;
}