SPFA

gistfile1.txt

#include <iostream>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

long long n, k;
map<string,long long> M;
long long Hp[1111];

long long Head[1111], Next[41111], w[41111], V[41111];
long long TTot;

void AddEdge(long long s,long long t,long long c) {
	Next[++TTot] = Head[s] ;
	Head[s] = TTot;
	w[TTot] = c;
	V[TTot] = t;
}

//#define debug(x) cout << #x << " " << x <<endl
#define mp make_pair
const long long INF = 1000000000000000000;
string Name[5111];
typedef pair<pair<long long, long long>, pair<long long, long long> > piii;
//               dis , happiness , totEdge, totWays

long long Ntot = 0;
piii Dis[5111];
bool inq[5111];
long long pre[5111];

string Ans[1111];
void Spfa(long long S,long long T) {
	queue<long long> Q;
	Q.push(S);	
	for(long long i = 1; i <= 1111; ++i) Dis[i] = mp(mp(INF,0),mp(INF,0));
	Dis[S] = mp(mp(0,0),mp(0,1));
	inq[S] = 1;
	while( Q.size() ) {
		long long now = Q.front(); inq[now] = 0;Q.pop();
		for(long long i = Head[now]; i!=0 ; i = Next[i]) {
			long long pt = V[i]; 
			if (Dis[pt].first.first > Dis[now].first.first + w[i]) {
				pre[pt] = now;
				Dis[pt].first.first = Dis[now].first.first + w[i];
				Dis[pt].first.second = Dis[now].first.second + Hp[pt];
				Dis[pt].second.first = Dis[now].second.first + 1;
				Dis[pt].second.second = Dis[now].second.second;
				if (!inq[pt]) {
					inq[pt] = 1;
					Q.push(pt);
				}
			}else if (Dis[pt].first.first == Dis[now].first.first + w[i]) {
				Dis[pt].second.second += Dis[now].second.second;
				if (Dis[pt].first.second < Dis[now].first.second + Hp[pt]) {
					if (!inq[pt]) {
						inq[pt] = 1;
						Q.push(pt);
					}
					pre[pt] = now;
					Dis[pt].first.second = Dis[now].first.second + Hp[pt];
				}else if (Dis[pt].first.second == Dis[now].first.second + Hp[pt]) {
					if (Dis[pt].second.first > Dis[now].second.first + 1) {
						Dis[pt].second.first = Dis[now].second.first + 1;
						if (!inq[pt]) {
							inq[pt] = 1;
							Q.push(pt);
						}
						pre[pt] = now;
					}
				}
			}
		}
	}
	//for(long long i = 1; i <= Ntot; ++i) debug(Dis[i].second.first);
	//if (Dis[T].second.first == 0) while(1);
	//if (Dis[T].first.first == INF) while(1);
	//if (Dis[T].second.second == 0) while(1);
	cout << Dis[T].second.second << " " << Dis[T].first.first << " " << Dis[T].first.second << " " << Dis[T].first.second / Dis[T].second.first <<endl;
	long long Now = M["ROM"];
	long long Ftot = 0;
	while(pre[Now]!=0) Ans[++Ftot] = Name[pre[Now]], Now = pre[Now];
	for(long long i = Ftot; i >= 1; --i) cout << Ans[i]<<"->";
	cout << "ROM" <<endl;
}

int main()
{
	string S;
	cin >> n >> k >> S;
	
	long long Times = n-1;
	M[S] = ++Ntot;
	Name[M[S]] = S;
	while(Times--) {
		string s;long long  hp; 
		cin >> s >> hp;
		M[s] = ++Ntot;
		Name[M[s]] = s;
		Hp[M[s]] = hp;
	}
	for(long long i = 1; i <= k; ++i) {
		string s1, s2; long long c;
		cin >> s1 >> s2 >> c;
		AddEdge(M[s1], M[s2], c);
		AddEdge(M[s2], M[s1], c);
	}
	if ( S == "ROM" ) while(1);
	Spfa(M[S],M["ROM"]);
	return 0;
}