基于Dijsktra算法的最短路径求解

数据结构习题解析与实验指导     实验7

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int MAX = 1e6+100;
char x,y;
map<char,int> mp;
map<int,char> mpp;
struct hh{
	int u,v,w,nt;
	hh(){}
	hh(int ww,int vv){
		w=ww;
		v=vv;
	}
	bool operator<(const hh &q) const{
		return w>q.w;
	}
}a[MAX];
int tot,head[MAX],dis[MAX],bian[MAX];
void add(int u,int v,int w){
	a[tot].u=u;
	a[tot].v=v;
	a[tot].w=w;
	a[tot].nt=head[u];
	head[u]=tot++;
}
void init(){
	memset(head,-1,sizeof(head));
	memset(dis,inf,sizeof(dis));
	memset(bian,0,sizeof(bian));
}
void print(int v){
	if(bian[v]==0){
		cout << mpp[v] << " ";
		return;
	}
	print(bian[v]);
	cout << mpp[v] << " ";
	return;
}
void dij(int s){
	priority_queue<hh> q;
	dis[s]=0;
	q.push(hh(dis[s],s));
	while(!q.empty()){
		hh tmp;
		tmp=q.top();
		q.pop();
		int u=tmp.v;
		if(u==mp[y]) break;
		for (int i = head[u]; ~i;i=a[i].nt){
			int v=a[i].v;
			if(dis[v]>dis[u]+a[i].w){
				dis[v]=dis[u]+a[i].w;
				bian[v]=u;
				q.push(hh(dis[v],v));
			}
		}
	}
}
int main(){
	int n,m;
	while(cin >> n >> m){
		if(n==0&&m==0) break;
		init();
		mp.clear();
		mpp.clear();
		int cnt=1;
		for (int i = 0; i < n;i++){
			char ch;
			cin >> ch;
			mp[ch]=cnt;
			mpp[cnt++]=ch;
		}
		for (int i = 0; i < m;i++){
			char u,v;
			int w;
			cin >> u >> v >> w;
			add(mp[u],mp[v],w);
			add(mp[v],mp[u],w);
		}
		cin >> x >> y;
		dij(mp[x]);
		cout << dis[mp[y]] << endl;
		print(mp[y]);
		cout << endl;
	}
	return 0;
}
/*
3 3
A B C
A B 1
B C 1
C A 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
D E 20
E F 60
D F 10
A F
0 0
*/