数据结构习题解析与实验指导 实验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
*/