PAT 1087【二级最短路】

二级最短路+二级最短路，就是DP过程吧。
代码稍微注释一些，毕竟贴代码不好。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=4e4+10;
struct asd{
	int cost;
	int to;
	int next;
}e[N];
int head[220],tol,tot;
int n,m,w[220];
map<string,int>mp;
map<int,string>ip;

int GetID(string s)
{
	if(mp.find(s)!=mp.end()) return mp[s];
	return mp[s]=++tot;
}
void init()
{
	tol=tot=0;
	memset(head,-1,sizeof(head)); 
}
void add(int u,int v,int cost)
{
	e[tol].cost=cost;
	e[tol].to=v;
	e[tol].next=head[u];
	head[u]=tol++;
}

queue<int>q;
vector<int>xs;
bool vis[220];
int pre[N];		//记录路径 
int dis[220];	//距离花费 
int hap[220];	//到位置 v 的最大开心值 
int all[220];	//到位置 v 的所有开心值总和 
int rotu[220];	//到位置 v 的路线条数 
int num[220];	//到位置 v 的结点个数 
int ave[220];	//到位置 v 的最大平均数 
void SPFA(int s,int t)		//利用SPFA算法（最短路比较喜欢的算法，有可能会卡常数。 
{
	xs.clear();
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++)
	{
		vis[i]=false;
		dis[i]=INF;
		num[i]=rotu[i]=all[i]=hap[i]=0;
	}
	pre[s]=-1;
	rotu[s]=1;
	vis[s]=true;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=false;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].cost)		//一旦这个花费大了，所有都要更新 
			{
				pre[v]=u;
				dis[v]=dis[u]+e[i].cost;
				all[v]=hap[v]=hap[u]+w[v];
				rotu[v]=rotu[u];
				num[v]=num[u]+1;
				ave[v]=all[v]/num[v];
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
			else if(dis[v]==dis[u]+e[i].cost)	//花费相同，更新路径 
			{
				rotu[v]+=rotu[u];
				if(hap[v]<hap[u]+w[v])			//开心值取大的 
				{
					pre[v]=u;
					all[v]=hap[v]=hap[u]+w[v];
					num[v]=num[u]+1;
					ave[v]=all[v]/num[v];
				}
				else if(hap[v]==hap[u]+w[v])	//开心值相同，判断最大平均数 
				{
					int t_all,t_ave,t_num;
					t_all=hap[u]+w[v];
					t_num=num[u]+1;
					t_ave=t_all/t_num;
					ave[v]=max(ave[v],t_ave);
				}
			}
		}
	}
	int x=t;
	while(x!=-1)
	{
		xs.push_back(x);
		x=pre[x];
	}
	printf("%d %d %d %d
",rotu[t],dis[t],hap[t],ave[t]);
	int sz=xs.size();
	for(int i=sz-1;i>=0;i--)
	{
		if(i!=sz-1) cout<<"->";
		cout<<ip[xs[i]];
	}
}

int main()
{
	string be,st;
	int x,idx,idy,id,s,t;
	cin>>n>>m>>be;
	s=GetID(be);
	ip[s]=be;
	for(int i=1;i<n;i++)
	{
		cin>>be>>x;
		id=GetID(be);ip[id]=be;
		w[id]=x;
	}
	init();
	while(m--)
	{
		cin>>be>>st>>x;
		idx=GetID(be);
		idy=GetID(st);
		add(idx,idy,x);
		add(idy,idx,x);
	}
	t=mp["ROM"];
	SPFA(s,t);
	return 0;
}