HDU 2544 最短路(链式前向星+dijkstra优先队列优化)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

第一次用队列优化加链式前向星，所以找了道模板题来练手，体验感不错..

---

AC代码：

代码语言：javascript复制

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#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<Node> 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("%dn",dis[n]);
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0)break;
		init();
		for(int i=0;i<m;i  ){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		dijkstra(1);
	}
	return 0;
}

队列 优化

0 人点赞