HDU 2544 최 단 로 (체인 전방 향 성 + dijkstra 우선 대기 열 최적화)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2544
처음으로 대열 로 체인 식 전방 향 성 을 최적화 시 켰 기 때문에 템 플 릿 문 제 를 찾 아 연습 을 했 는데 체험 감 이 좋 았 다.
AC 코드:

#include 
#include 
#include 
#include 
#define maxn 10005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,num;
struct Node{
	int to;
	int w;
	int Next;
	bool operator < (const Node &a) const{
		return a.w < w;
	}
}Edge[maxn],Now,Next;
int Head[maxn];

void init(){
	memset(Head,-1,sizeof(Head));
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].to = v;
	Edge[num].w = w;
	Edge[num].Next = Head[u];
	Head[u] = num++;
}

void dijkstra(int ans){
	bool vis[maxn];
	int dis[maxn];
	memset(dis,inf,sizeof(dis));
	memset(vis,false,sizeof(vis));
	priority_queue q;
	Now.to = ans;
	dis[ans] = 0;
	q.push(Now);
	while(!q.empty()){
		Now = q.top();
		q.pop();
		int flag = Now.to;
		if(vis[flag])
			continue;
		vis[flag] = true;
		for(int i = Head[flag]; i != -1; i = Edge[i].Next){
			int u = Edge[i].to;
			if(!vis[u] && dis[u] > dis[flag] + Edge[i].w){
				dis[u] = dis[flag] + Edge[i].w;
				Next.to = u;
				Next.w = dis[u];
				q.push(Next);
			}
		}
	}
	printf("%d
",dis[n]);
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0)break;
		init();
		for(int i=0;i