[数据结构与算法]7-29 直捣黄龙 (30 分)---dijkstra简单变形

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
#include <stack>
#include <functional>
using namespace std;

map<string,int>S;
int idx=0;
map<int,string>str;
int n,k;
int w[210],d[210][210];
int dist[210],cnt[210],kill[210],dist_cnt[210];
int pre[210];
bool vis[210];
int st,ed;
int get(string s)
{
	if(S.count(s))return S[s];
	S[s]=++idx;
	str[S[s]]=s;
	return S[s];
}

void dij()
{
    for(int i=0;i<210;i++)dist_cnt[i]=1;
	memset(dist,0x3f,sizeof dist);
	memset(cnt,1,sizeof cnt);
	memset(vis,0,sizeof vis);
	memset(kill,0,sizeof kill);
	dist[st]=0;
	kill[st]=w[st];
	cnt[st]=1;
	pre[st]=0;
	for(int i=0;i<n-1;i++)
	{
		int u=-1;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&(u==-1||dist[u]>dist[j]))
					u=j;
		
				
		for(int v=1;v<=n;v++)
		{
			if(dist[u]+d[u][v]<dist[v])
			{
				dist[v]=dist[u]+d[u][v];
				cnt[v]=cnt[u]+1;
				kill[v]=kill[u]+w[v];
				pre[v]=u;
				dist_cnt[v]=dist_cnt[u];
			}
			else if(dist[u]+d[u][v]==dist[v]&&cnt[v]<cnt[u]+1)
			{
			    dist_cnt[v]+=dist_cnt[u];
				cnt[v]=cnt[u]+1;
				kill[v]=kill[u]+w[v];
				pre[v]=u;
			}
			else if(dist[u]+d[u][v]==dist[v]&&cnt[v]==cnt[u]+1&&kill[v]<kill[u]+w[v])
			{
			    dist_cnt[v]+=dist_cnt[u];
				kill[v]=kill[u]+w[v];
				pre[v]=u;
				cnt[v]=cnt[u]+1;
			}
			else if(dist[u]+d[u][v]==dist[v])dist_cnt[v]+=dist_cnt[u];
		}
		vis[u]=true;
	}
}

signed main()
{
    memset(d,0x3f,sizeof d);
	cin>>n>>k;string a,b;cin>>a>>b;
	st=get(a);ed=get(b);
	for(int i=1,x;i<n;i++)
	{
		string name;cin>>name>>x;
		w[get(name)]=x;
	}
	for(int i=0,dis;i<k;i++)
	{
		string a,b;
		cin>>a>>b>>dis;
		d[get(a)][get(b)]=dis;
		d[get(b)][get(a)]=dis;
		//cout<<get(a)<<"  "<<get(b)<<"  "<<dis<<endl;
	}
	dij();
	vector<string>path;
	int t=ed;
	while(pre[t])
	{
	    path.push_back(str[t]);
	    t=pre[t];
	}
	path.push_back(str[st]);
	reverse(path.begin(),path.end());
	for(int i=0;i<path.size();i++)
	{
	    if(i)cout<<"->";
	    cout<<path[i];
	}
	cout<<endl;
	cout<<dist_cnt[ed]<<" "<<dist[ed]<<" "<<kill[ed]<<endl;
}