//Dijkstra算法只是给了我们遍历求最短路径的方法，但是通过这个遍历方法我们可以做更多其他的
//事情，而这些就是灵活运用的部分。
//思路：Dijkstra是用来球最短路径的，该题可以把cost当作最短路径来看待，然后就是根据本题因
//地制宜，求出最小成本到达ROM的同时，记录有多少不同的路径以该最小成本到达，其中最优的路径
//是那一条，不需要一下子给出整条路径，只需要有链表能把路径给带出来就行了。
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <limits>
using namespace std;
struct Point {
	int k;//城市编号
	int routes=0;//有几条线路可以到达该点
	int depth=0;//路径中第几个点
	int p=-1;//推荐路线的父节点
	int accum_happy=0;//到该点积累的快乐指数，与depth结合可以计算平均快乐指数
	int accum_cost = numeric_limits<int>::max();
	bool visited = false;
};
vector<Point> points;
map<string, int> Cities;
//map的开销会比较大，内存占用也比较大，所以使用一个map，其他都可以用vector了，
//由城市名得到索引。
vector<string> Index;//与Cities配合，它是由索引得到城市名
vector<int> Happiness;
vector < vector<int>> Costs;
vector<vector<int>> adjacency;
void print_path(int end);
void dijkstra(int N);
inline int find_least(vector<Point> &points) {
	int index = 0, minor = numeric_limits<int>::max();
	for (int j = 1;j < points.size();++j) {
		if (points[j].visited==false&&points[j].accum_cost < minor) {
			minor = points[j].accum_cost;
			index = j;
		}
	}
	return index;
}
inline void change(int least, int j) {
	points[j].p = least;
	points[j].accum_cost = points[least].accum_cost + Costs[least][j];
	points[j].accum_happy = points[least].accum_happy + Happiness[j];
	points[j].depth = points[least].depth + 1;
	points[j].routes = points[least].routes;
}
inline void update(int least, int j) {
	Point &former = points[least];
	Point &current = points[j];
	current.routes += former.routes;
	if (former.accum_happy + Happiness[j]>current.accum_happy) {
		current.accum_happy = former.accum_happy + Happiness[j];
		current.p = least;
		current.depth = former.depth + 1;
	}
	else if (former.accum_happy + Happiness[j] == current.accum_happy) {
		if (former.depth + 1 > current.depth) {
			current.p = least;
			current.depth = former.depth + 1;
		}
	}
}
void dijkstra(int N) {
	for (int i = 0;i < N;++i) {
		int least = find_least(points);
		Point &least_p = points[least];
		least_p.visited = true;
		vector<int> branch = adjacency[least];
		for (int j = 0;j < branch.size();++j) {
			if (least_p.accum_cost + Costs[least][branch[j]] < points[branch[j]].accum_cost) {
				change(least, branch[j]);
			}
			else if (least_p.accum_cost + Costs[least][branch[j]] == points[branch[j]].accum_cost) {
				update(least, branch[j]);
			}
		}
	}
}
int main() {
	int N, K;
	string start;
	while (cin >> N >> K >> start) {
		points.resize(N);
		points[0].accum_cost = 0;
		points[0].routes = 1;
		Index.resize(N);
		Happiness.resize(N);
		Costs.resize(N, vector<int>(N));
		adjacency.resize(N);
		Cities[start] = 0;
		Index[0] = start;
		Happiness[0] = 0;
		string city;
		int happy;
		for (int i = 1;i < N;++i) {
			points[i].k = i;
			cin >> city >> happy;
			Cities[city] = i;
			Index[i] = city;
			Happiness[i] = happy;
		}
		string city1, city2;
		int cost;
		for (int i = 0;i < K;++i) {
			cin >> city1 >> city2 >> cost;
			Costs[Cities[city1]][Cities[city2]] = cost;
			Costs[Cities[city2]][Cities[city1]] = cost;
			adjacency[Cities[city1]].push_back(Cities[city2]);
			adjacency[Cities[city2]].push_back(Cities[city1]);
		}

		//至此数据接收完毕
		dijkstra(N);
		int end = Cities["ROM"];
		cout << points[end].routes << " " << points[end].accum_cost << " " << points[end].accum_happy << " " << points[end].accum_happy / points[end].depth << endl;
		print_path(end);
	}
}
void print_path(int end) {
	Point p = points[end];
	if (p.p != -1) {
		print_path(p.p);
		cout << Index[end];
		if (Cities["ROM"] != end) {
			cout << "->";
		}
		else {
			cout << endl;
		}
	}
	else {
		cout << Index[end] << "->";
	}
}

import java.util.HashMap;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();//numbers of city
		int k = in.nextInt();//numbers of routes
		String start = in.next();//start city
		int[] costs = new int[n];//每一个点到顶点的cost
		int[] hpns = new int[n];//每一个点到顶点的happiness值
		int[] steps = new int[n];//每一条路径的节点数，不包括头节点
		int[] routes = new int[n];//到达每个点的路由数量
		int[] parent = new int[n];//每一个结点的父节点
		int[][] M = new int[n][n];//邻接矩阵
		HashMap<String, Integer> index = new HashMap<String, Integer>();//记录每个城市的下标
		boolean[] visited = new boolean[n];//标记已经访问的结点
		int[] h = new int[n];//每个城市的幸福值
		String[] names = new String[n];//每个城市的名称
		routes[0] = 1;
		parent[0] = -1;
		index.put(start, 0);
		names[0] = start;
		//初始化 
		for(int i = 1;i<n;i++){
			costs[i] = Integer.MAX_VALUE;
			hpns[i] = Integer.MIN_VALUE;
			names[i] = in.next();
			index.put(names[i], i);
			h[i] = in.nextInt();
		}
		int end = index.get("ROM");
		
		for(int i = 0;i<k;i++){
			int s = index.get(in.next());
			int e = index.get(in.next());
			int cost = in.nextInt();
			M[s][e] = cost;
			M[e][s] = cost;
		}
		for(int t = 0;t<n;t++){
			int v = -1;
			for(int i = 0;i<n;i++){
				if (!visited[i] && ((v < 0) || (costs[i] < costs[v])))
	                v = i;
			}
			visited[v] = true;
			for(int i = 0;i<n;i++){
				if(!visited[i]&&M[v][i]!=0){
					int cost = costs[v] + M[v][i];
					int happy = hpns[v] + h[i];
					int step = steps[v] + 1;
					boolean flag = false;
					if(cost<costs[i]){
						costs[i] = cost;
	                    routes[i] = routes[v];
	                    flag = true;
					}else if(cost==costs[i]){
						routes[i] += routes[v];
						if(happy>hpns[i]){
							flag = true;
						}else if(happy==hpns[i] && step<steps[i]){
							flag = true;
						}
					}
					if(flag){
						costs[i] = cost;
						hpns[i] = happy;
	                    steps[i] = step;
						parent[i] = v;
					}
				}
			}
		}
		int total = steps[end];
		int happiness = hpns[end];
		int avg = happiness/total;
		total++;
		System.out.println(routes[end]+" "+costs[end]+" "+happiness+" "+avg);
		String[] result = new String[total];
		int j = total-1;
		while(end!=-1){
			result[j--] = names[end];
			end = parent[end];
		}
		for(int i = 0;i<result.length-1;i++){
			System.out.print(result[i]+"->");
		}
		System.out.println(result[total-1]);
	}
}

#pragma warning (disable: 4996)
#include <cstdio>
#include <cstdlib>

//从这里开始看
//本方法没用到Dijkstra,直接DFS,性能上略差,但是思路非常简单
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

#define MAX 1000
#define _INF 10000000

int N, K; string start;

map<string, int> cityIndex; string city[MAX];//城市编号相互映射，基本功
int happy[MAX]; int cost[MAX][MAX]; 
bool visited[MAX];
vector<string> tmpRoute, bestRoute;//vector最猛的用法就是看作“栈”
int num = 0, costMin = _INF, happyMax = 0, averHappyMAX = 0;//最值变量
int cur_cost = 0, cur_happy = 0, cur_len = 0;//动态更新变量
void updateBestRoute() {
	happyMax = cur_happy;
	averHappyMAX = cur_happy / cur_len;
	bestRoute = tmpRoute;
}

void DFS(int i) {//DFS要写得尽量对称才有美感
	visited[i] = true; tmpRoute.push_back(city[i]);
	if (costMin >= cur_cost) {//提前剪枝
		if (city[i] == "ROM") {
			if (costMin > cur_cost) {
				costMin = cur_cost;
				num = 1;
				updateBestRoute();
			}
			else {
				num++;
				if (happyMax < cur_happy ||
					happyMax == cur_happy &&
					averHappyMAX < cur_happy / cur_len) {
					updateBestRoute();
				}
			}
		}
		else if (costMin > cur_cost) {//剪枝,剪不剪枝差距很大
			for (int j = 0; j < N; ++j) {
				if (visited[j] == false && cost[i][j] > 0) {
					cur_cost += cost[i][j];
					cur_happy += happy[j];
					++cur_len;
					DFS(j);
					cur_cost -= cost[i][j];
					cur_happy -= happy[j];
					--cur_len;
				}
			}
		}
	}
	visited[i] = false; tmpRoute.pop_back();
}

int main()
{
	cin >> N >> K >> start;
	cityIndex[start] = 0;
	city[0] = start;
	happy[0] = 0;
	for (int i = 1; i < N; ++i) {
		cin >> city[i] >> happy[i];
		cityIndex[city[i]] = i;
	}
	string city1, city2; int c;
	for (int i = 0; i < K; ++i) {
		cin >> city1 >> city2 >> c;
		cost[cityIndex[city1]][cityIndex[city2]] = c;
		cost[cityIndex[city2]][cityIndex[city1]] = c;
	}

	fill(visited, visited + 500, false);
	DFS(0);

	cout << num << " " << 
		costMin << " " << 
		happyMax << " " << 
		averHappyMAX << endl;
	for (auto it = bestRoute.begin(); it != bestRoute.end(); ++it) {
		cout << *it; if (*it != "ROM")cout << "->";
	}
	return 0;
}

19-8-14 13 50

All Roads Lead to Rome (30)
最短路
用map来映射
dijstra记录最短路(使用pre数组)
在pre的图（DAG图）上做DFS， 输出符合条件的路径即可
写了点注释

#include<bits/stdc++.h>

using namespace std;
// Typedef 
typedef map<string, int> msi;
typedef pair<int, int> pii;

// Const
const int N = 500+10;
const int inf = 0x3f3f3f3f;

// IO
int n,m;//i
string s, t("ROM");
int val[N];
vector<pii> G[N];
msi mp;
string rmp[N];

int ans[N], max_ans[N];//o
int ans_sum, ans_cnt, ans_top;

// DataStruct
int cnt;
priority_queue<pii, vector<pii>, greater<pii> > que;
int dist[N], vis[N];
vector<int> pre[N];

// Func
void init()
{
    mp.clear();
    rmp[0] = s;val[0] = 0;
    for(int i=0;i<=n;i++)G[i].clear();
    ans_cnt = cnt = 0;ans_sum = -inf;
}

void dij()
{
    while(!que.empty())que.pop();
    fill(vis,vis+n,0);
    fill(dist,dist+n,inf);
    dist[mp[s]] = 0;
    que.push((pii){0, mp[s]});
    while(!que.empty())
    {
        pii tp = que.top();que.pop();
        int u = tp.second;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i=0;i<G[u].size();i++)
        {
            int v = G[u][i].first, cost = G[u][i].second;
            if (dist[u] + cost < dist[v])
            {
                dist[v] = dist[u] + cost;
                que.push((pii){dist[v], v});
                pre[v].clear();
                pre[v].push_back(u);
            }
            else if (dist[u] + cost == dist[v])
            {
                pre[v].push_back(u);
            }
        }
    }
}

void dfs(int u, int fa, int top)
{
    if (u == mp[s])
    {
        ans_cnt++;
        int sum = 0;
        for(int i=0;i<top;i++)
            sum += val[ans[i]];
        if (sum > ans_sum || (sum == ans_sum && top < ans_top))
        {
            ans_sum = sum;
            for(int i=0;i<top;i++)
            {
                max_ans[i] = ans[top-1-i];
            }
            ans_top = top;
        }
        return;
    }
    for(int i=0;i<pre[u].size();i++)
    {
        int v = pre[u][i];
        if (v == fa) continue;
        ans[top] = pre[u][i];
        dfs(v, u, top+1);
    }
}

int main()
{
    //freopen("2.in","r",stdin);
    ios::sync_with_stdio(0);
    while(cin>>n>>m>>s)
    {
        //init()
        init();
        string x,y;
        int v;
        rmp[cnt] = s;
        mp[s] = cnt++;
        //i
        for(int i=0;i<n-1;i++)
        {
            cin>>x>>v;
            rmp[cnt] = x;
            val[cnt] = v;
            mp[x] = cnt++;
        }
        for(int i=0;i<m;i++)
        {
            cin>>x>>y>>v;
            G[mp[x]].push_back((pii){mp[y], v});
            G[mp[y]].push_back((pii){mp[x], v});
        }
        //deal
        dij();
        ans[0] = mp[t];
        dfs(mp[t], -1, 1);
        //o
        cout<<ans_cnt<<' '<<dist[mp[t]]<<' ';
        cout<<ans_sum<<' '<<ans_sum/(ans_top-1)<<endl;
        for(int i=0;i<ans_top-1;i++)
        {
            cout<<rmp[max_ans[i]]<<"->"; 
        }
        cout<<rmp[max_ans[ans_top-1]]<<endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=210;
const int INF=10000000;
bool vis[maxn]={false};
int n,m,G[maxn][maxn],d[maxn],weight[maxn];   //n为结点数，m为边数，weight[]为点权
int numPath=0,maxW=0;double maxAvg=0;         //numPath为最短路径条数，maxW为最大的点权之和，maxAvg为最大的平均点权
vector<int> pre[maxn],path,tempPath;          //前驱，临时路径，最优路径
map<string,int> StoI;
map<int,string> ItoS;
void Dijkstra(int s){
    fill(d,d+maxn,INF);d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,min=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<min){
                u=j;min=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    pre[v].clear();            //清空pre[v]
                    pre[v].push_back(u);
                }
                else if(d[u]+G[u][v]==d[v])
                    pre[v].push_back(u);       //u也是v的前驱之一
            }
        }
    }
}
void DFS(int v){
    tempPath.push_back(v);                     //当前点加入临时路径
    if(v==0){                                  //递归边界（到了Dijkstra的起点）
        numPath++;                             //最短路径条数加1
        int tempW=0;                           //临时路径tempPath上的点权之和
        for(int i=tempPath.size()-2;i>=0;i--){ //倒着访问（排除无点权的起点）
            int id=tempPath[i];
            tempW+=weight[id];
        }
        double tempAvg=1.0*tempW/(tempPath.size()-1);//临时路径上的平均点权
        if(tempW>maxW){                        //当前路径点权之和更大
            maxW=tempW;
            maxAvg=tempAvg;
            path=tempPath;                     //覆盖最优路径path
        }
        else if(tempW==maxW&&tempAvg>maxAvg){  //点权之和相同，当前路径平均点权更大
            maxAvg=tempAvg;
            path=tempPath;
        }
        tempPath.pop_back();                   //处理完此结点后从临时路径中删除（回溯）
        return;
    }
    for(int i=0;i<pre[v].size();i++)           //继续DFS当前结点v的各个前驱
    DFS(pre[v][i]);
    tempPath.pop_back();                       //处理完此结点后从临时路径中删除（回溯）
}
int main(){
    fill(G[0],G[0]+maxn*maxn,INF);
    string start,s1,s2;
    cin>>n>>m>>start;
    StoI[start]=0;
    ItoS[0]=start;
    for(int i=1;i<=n-1;i++){
        cin>>s1>>weight[i];
        StoI[s1]=i;
        ItoS[i]=s1;
    }
    for(int i=0;i<m;i++){
        cin>>s1>>s2;
        int c1=StoI[s1],c2=StoI[s2];
        cin>>G[c1][c2];
        G[c2][c1]=G[c1][c2];
    }
    Dijkstra(0);                               //0（即start）为起点
    int rom=StoI["ROM"];
    DFS(rom);                                  //从终点开始以pre前驱为指针获取最优路径
    printf("%d %d %d %d\n",numPath,d[rom],maxW,(int)maxAvg);
    for(int i=path.size()-1;i>=0;i--){         //倒着输出（之前DFS是从终点开始加入路径）
        cout<<ItoS[path[i]];
        if(i>0) cout<<"->";
    }
    return 0;
} 

//dfs1求出到目的点的最小花费mincost
//dfs2更新题目要求的信息
//随便说一下Dijkstra是可以做，但是n只有200显然直接爆搜就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e2+5,INF=1e9;
int n,m,idstart,idend,happiness[maxn],cost[maxn][maxn];
map<string,int> mp;
string name[maxn],str_start,str_end;
vector<int> G[maxn],anspath,curpath;
int cnt,mincost=INF,maxhappiness=-INF,vis[maxn];
int ID(const string &str){
    int num=mp.size();
    if(mp.find(str)!=mp.end()) return mp[str];
    else{
        name[num+1]=str;
        return mp[str]=num+1;    
    } 
}
void dfs1(int cur,int curcost){
    if(curcost>mincost) return ;
    if(cur==idend){
        mincost=min(mincost,curcost);
        return ;
    }
    vis[cur]=1;
    for(int i=0;i<G[cur].size();++i){
        int v=G[cur][i];
        if(!vis[v]){
            dfs1(v,curcost+cost[cur][v]);
            vis[v]=0;
        }
    }
}
void dfs2(int cur,int curcost,int curhappiness){
    vis[cur]=1;curpath.push_back(cur);
    if(curcost>mincost) return ;
    if(cur==idend){
        if(curcost==mincost) ++cnt;
        if(curcost==mincost&&curhappiness>maxhappiness){
            maxhappiness=curhappiness;anspath=curpath;return ;
        }if(curcost==mincost&&curhappiness==maxhappiness){
            if(curhappiness/(curpath.size()-1)>maxhappiness/(anspath.size()-1))
                anspath=curpath;
            return ;            
        }
        return ;
    }
    for(int i=0;i<G[cur].size();++i){
        int v=G[cur][i];
        if(!vis[v]){
            dfs2(v,curcost+cost[cur][v],curhappiness+happiness[v]);
            vis[v]=0;curpath.pop_back();
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>str_start;idstart=ID(str_start);
//cout<<idstart<<"******"<<endl;
    for(int i=1;i<=n-1;++i){
        string tmp;int happy;
        cin>>tmp>>happy;
        happiness[ID(tmp)]=happy;
    }
    idend=ID("ROM");
    for(int i=1;i<=m;++i){
        string tmp1,tmp2;int cst;
        cin>>tmp1>>tmp2>>cst;
        int x=ID(tmp1),y=ID(tmp2);
        cost[x][y]=cst;cost[y][x]=cst;
        G[x].push_back(y);G[y].push_back(x);
    }
//cout<<name[idstart]<<endl;
//cout<<idstart<<endl;
    dfs1(idstart,0);
    dfs2(idstart,0,0);
    cout<<cnt<<" "<<mincost<<" "<<maxhappiness<<" "<<maxhappiness/(anspath.size()-1)<<endl;
    for(int i=0;i<anspath.size();++i){
        string nme=name[anspath[i]];
        if(i==0) cout<<nme;
        else cout<<"->"<<nme;
    }
    return 0;
} 

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


const int N = 210, L = 4;
struct Name {
    char s[L];
    Name() {}
    Name(const char *ss)
    {
        memcpy(s, ss, sizeof(s));
    }
    bool operator <(const Name &rhs) const
    {
        return strcmp(s, rhs.s) < 0;
    }
};
const Name ROM = Name("ROM");
struct Edge {
    int from, to, dis;
    Edge(int f, int t, int d): from(f), to(t), dis(d) {}
};
struct Graph {
    static const int INF = 1000000000;
    vector<int> G[N];
    vector<Edge> edges;
    stack<int> route;
    int n, m;
    int cost, cnt = 0, maxh = 0, minD, dest;
    int inq[N];
    int d[N];
    int happ[N];
    void init(int nn)
    {
        n = nn;
        edges.clear();
        memset(happ, 0, sizeof(happ));
        for(int i = 0; i < n; i++)
            G[i].clear();
    }
    void AddEdge(int f, int t, int d)
    {
        edges.push_back(Edge(f, t, d));
        edges.push_back(Edge(t, f, d));
        m = edges.size();
        G[f].push_back(m - 2);
        G[t].push_back(m - 1);
    }
    int Mindis(int s, int t)
    {
        memset(inq, 0, sizeof(inq));
        for(int i = 0; i < n; i++)
            d[i] = INF;
        d[s] = 0;
        queue<int> q;
        inq[s] = 1;
        q.push(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = 0;
            for(int i = 0; i < G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if(d[e.to] > d[u] + e.dis) {
                    d[e.to] = d[u] + e.dis;
                    if(!inq[e.to]) {
                        inq[e.to] = 1;
                        q.push(e.to);
                    }
                }
            }
        }
        cost = d[t];
        return d[t];
    }
    int Dfs(int from, int depth, int h)
    {
        if(from == dest) {
            cnt++;
            h += happ[from];
            if(h < maxh) {
                return 0;
            }
            if(h > maxh) {
                maxh = h;
                minD = depth;
                while(!route.empty())
                    route.pop();
                route.push(from);
                return 1;
            } else if(h == maxh && depth < minD) {
                minD = depth;
                while(!route.empty())
                    route.pop();
                route.push(from);
                return 1;
            } else {
                return 0;
            }
        }
        int better = 0;
        for(int i = 0; i < G[from].size(); i++) {
            Edge &e = edges[G[from][i]];
            if(d[e.to] <= cost && (d[e.to] == d[from] + e.dis)) {
                if(Dfs(e.to, depth + 1, h + happ[from])) {
                    route.push(from);
                    better = 1;
                }
            }
        }
        if(better)
            return 1;
        else
            return 0;
    }
};

int n, m;
map<Name, int> num;
vector<Name> names;
Graph g;
int main()
{
    char s1[L], s2[L];
    scanf("%d %d %s\n", &n, &m, s1);
    g.init(n);
    num[Name(s1)] = names.size();
    names.push_back(Name(s1));
    g.happ[0] = 0;
    for(int i = 1; i < n; i++) {
        int happ;
        scanf("%s %d\n", s1, &happ);
        Name name = Name(s1);
        int j = num[name] = names.size();
        names.push_back(name);
        g.happ[j] = happ;
    }
    for(int i = 0; i < m; i++) {
        int d;
        scanf("%s %s %d\n", s1, s2, &d);
        g.AddEdge(num[Name(s1)], num[Name(s2)], d);
    }
    g.Mindis(0, num[ROM]);
    g.dest = num[ROM];
    g.Dfs(0, 0, 0);

    printf("%d %d %d %d\n", g.cnt, g.cost, g.maxh, int(g.maxh / float(g.minD)));
    printf("%s", names[0].s);
    g.route.pop();
    while(!g.route.empty()) {
        printf("->%s", names[g.route.top()].s);
        g.route.pop();
    }
    printf("\n");
    return 0;
}

#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 200 + 2;
const int INF = 0x3f3f3f3f;
map<int, string> id2city;
map<string, int> city2id;

struct Dijkstra{
    struct Edge{
        int to, dist;
        Edge(int v, int l):to(v), dist(l){}
    };
    vector<Edge> G[maxn];
    int d[maxn], done[maxn], num[maxn];
    int pre[maxn], same[maxn];
    int city_happy[maxn], gain_happy[maxn];
    int ROM_ID;

    void init(int num, int m){
        for(int i=1; i<=num-1; i++){
            int happy;
            string city;
            cin >> city >> happy;
            int city_id = i;
            id2city[city_id] = city;
            city2id[city] = city_id;
            if(city == "ROM")   ROM_ID = city_id;
            city_happy[city_id] = happy;
        }
        for(int i=0; i<m; i++){
            int s;
            string c1, c2;
            cin >> c1 >> c2 >> s;
            int id1 = city2id[c1];
            int id2 = city2id[c2];
            Edge e(id2, s);
            G[id1].push_back(e);
            e.to = id1;
            G[id2].push_back(e);
        }
    }

    void dijkstra(int s){
        priority_queue<pii, vector<pii>, greater<pii> >Q;
        memset(d, INF, sizeof(d));
        memset(done, 0, sizeof(done));
        // memset(cost, INF, sizeof(cost));
        memset(pre, -1, sizeof(pre));
        memset(same, 0, sizeof(same));
        memset(num, INF, sizeof(num));
        memset(gain_happy, 0, sizeof(gain_happy));
        d[s] = 0;
        // cost[s] = 0;
        same[s] = 1;
        num[s] = 0;
        gain_happy[s] = 0;
        Q.push(make_pair(d[s], s));
        while(!Q.empty()){
            pii p = Q.top();
            Q.pop();
            int u = p.second;
            if(done[u]) continue;
            done[u] = 1;
            for(unsigned int i=0; i<G[u].size(); i++){
                Edge e = G[u][i];
                int v = e.to;
                if(done[v]) continue;
                if(d[v] > d[u] + e.dist){
                    d[v] = d[u] + e.dist;
                    pre[v] = u;
                    // cost[v] = cost[u] + e.dist;
                    same[v] = same[u];
                    num[v] = num[u] + 1;
                    gain_happy[v] = gain_happy[u] + city_happy[v];
                }
                else if(d[v] == d[u] + e.dist && gain_happy[v] < gain_happy[u] +city_happy[v]){
                    gain_happy[v] = gain_happy[u] + city_happy[v];
                    pre[v] = u;
                    same[v] += same[u];
                    num[v] = num[u] + 1;
                }
                else if(d[v] == d[u] + e.dist && gain_happy[v] == gain_happy[u] + city_happy[v] && num[v] > num[u] + 1){
                    pre[v] = u;
                    same[v] += same[u];
                    num[v] = num[u] + 1;
                }
                else if(d[v] == d[u] + e.dist)
                    same[v] += same[u];
                Q.push(make_pair(d[v], v));
            }
        }
    }

    void show_road(int s){
        if(s == 0) return;
        else{
            show_road(pre[s]);
            cout << "->" << id2city[s];
        }
    }

    void show_result(){
        printf("%d %d %d %d\n", same[ROM_ID], d[ROM_ID], gain_happy[ROM_ID], gain_happy[ROM_ID]/num[ROM_ID]);
        cout << id2city[0];
        show_road(ROM_ID);
        printf("\n");
    }
};

int main(){
    int n, k;
    string start;
    Dijkstra g;
    scanf("%d %d", &n, &k);
    cin >> start;
    int start_id = 0;
    id2city[start_id] = start;
    city2id[start] = start_id; 
    g.init(n, k);
    g.dijkstra(start_id);
    g.show_result();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=210;
const int INF=INT_MAX;

int n,k,num;
int G[Max][Max],c[Max],v[Max];
map<string,int> stringToint;
map<int,string> intTostring;
vector<int> pre[Max];
vector<int> path,temp;
bool visit[Max];

void Dijistra() {
	fill(c,c+Max,INF);
	c[0]=0;
	for(int i=0; i<n; i++) {
		int u=-1,Min=INF;
		for(int j=0; j<n; j++) {
			if(Min>c[j]&&!visit[j]) {
				Min=c[j];
				u=j;
			}
		}
		if(u==-1) return ;
		visit[u]=1;
		for(int v=0; v<n; v++) {
			if(!visit[v]&&G[u][v]!=INF) {
				if(c[v]>c[u]+G[u][v]) {
					c[v]=c[u]+G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				} else if(c[v]==c[u]+G[u][v]) {
					pre[v].push_back(u);
				}
			}
		}
	}
}

int Maxv=-1;
double Maxavg=0;
void DFS(int t) {
	if(t==0) {
		num++;
		temp.push_back(t);
		int value=0;
		for(int i=temp.size()-2; i>=0; i--) {
			int id=temp[i];
			value+=v[id];
		}
		double tempavg=1.0*value/(temp.size()-1);
		if(value>Maxv) {
			Maxv=value;
			Maxavg=tempavg;
			path=temp;
		} else if(value==Maxv&&tempavg>Maxavg) {
			Maxavg=tempavg;
			path=temp;
		}
		temp.pop_back();
		return ;
	}
	temp.push_back(t);
	for(int i=0; i<pre[t].size(); i++) {
		DFS(pre[t][i]);
	}
	temp.pop_back();
}

int main() {
	string s,city1,city2;
	int cost;
	cin>>n>>k>>s;
	stringToint[s]=0;
	intTostring[0]=s;
	fill(G[0],G[0]+Max*Max,INF);
	for(int i=1; i<n; i++) {
		cin>>city1>>v[i];
		stringToint[city1]=i;
		intTostring[i]=city1;
	}
	for(int i=0; i<k; i++) {
		cin>>city1>>city2>>cost;
		int u=stringToint[city1];
		int v=stringToint[city2];
		G[u][v]=G[v][u]=cost;
	}
	Dijistra();
	int t=stringToint["ROM"];
	DFS(t);
	printf("%d %d %d %d\n",num,c[t],Maxv,(int)Maxavg);
	for(int i=path.size()-1; i>=0; i--) {
		printf("%s",intTostring[path[i]].c_str());
		if(i>0) printf("->");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10;
const int INF=0x3f3f3f3f;
int n,k,start,endp,G[maxn][maxn],happy[maxn],dis[maxn];
bool visit[maxn];
map<string,int>stoiM;
map<int,string>itosM;
vector<int>pre[maxn];//记录前缀

int numCity=0;
int getId(string s){
    if(!stoiM.count(s)){
        stoiM[s]=numCity;
        itosM[numCity]=s;
        numCity++;
    }
    return stoiM[s];
}
//最短路径
void dijkstra(int s){
    fill(dis,dis+n,INF);
    fill(visit,visit+n,0);
    dis[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,min=INF;
        for(int j=0;j<n;j++){
            if(!visit[j] && dis[j]<min){
                min=dis[j];
                u=j;
            }
        }
        if(u==-1) return;
        visit[u]=true;
        for(int v=0;v<n;v++){
            if(!visit[v] && G[u][v]!=0){
                int tmp=dis[u]+G[u][v];
                if(tmp<dis[v]){
                    dis[v]=tmp;
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(tmp==dis[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
vector<int>tempPath;
vector<int>path;
int nums,maxHappy,maxMeanHappy,minCost=INF;
void DFS(int u){
    tempPath.push_back(u);
    if(u==start){//选择最优路径
        int curCost=0,curHappy=0,size=tempPath.size();
        double curMeanHappy=0;
        for(int i=0;i<size;i++){//path[0]是终点
            if(i<size-1){
                curCost+=G[tempPath[i]][tempPath[i+1]];
                curHappy+=happy[tempPath[i]];
            }
        }
        curMeanHappy=curHappy*1.0/(size-1);
        if(curCost<minCost){
            nums=1;
            path=tempPath;
            minCost=curCost;
            maxHappy=curHappy;
            maxMeanHappy=curMeanHappy;
        }else if(curCost==minCost){
            nums++;
            if(curHappy>maxHappy){
                path=tempPath;
                maxHappy=curHappy;
                maxMeanHappy=curMeanHappy;
            }else if(curHappy==maxHappy && curMeanHappy>maxMeanHappy){
                path=tempPath;
                maxMeanHappy=curMeanHappy;
            }
        }
    }
    //一直深搜到起点
    for(int v=0;v<pre[u].size();v++){
        DFS(pre[u][v]);
    }
    tempPath.pop_back();
}
int main()
{   
    string a,b;
    int c,id1,id2;
    cin>>n>>k>>a;
    start=getId(a);
    //输入happy
    for(int i=0;i<n-1;i++){
        cin>>a>>c;
        id1=getId(a);
        happy[id1]=c;
    }
    endp=stoiM["ROM"];
    //输入cost
    for(int i=0;i<k;i++){
        cin>>a>>b>>c;
        id1=stoiM[a];
        id2=stoiM[b];
        G[id1][id2]=G[id2][id1]=c;
    }
    dijkstra(start);
    DFS(endp);
    cout<<nums<<" "<<minCost<<" "<<maxHappy<<" "<<int(maxMeanHappy)<<endl;
    for(int i=path.size()-1;i>=0;i--){
        cout<<itosM[path[i]];
        if(i>0) cout<<"->";
    }
    return 0;
}

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
#define inf 0x3fffffff
#define N 210
int n,k,G[N][N],d[N],dis=0,cost[N]={0},ds,num[N],happy[N]={0},x=0;
string st,c1,c2;
bool vis[N];
vector<int> pre[N],path[N],ans;
map<string,int> Hash;
map<int,string> reHash;
void dijstra(){
	fill(vis,vis+N,false);
	fill(d,d+N,inf);
	d[0]=0,num[0]=1;
	for(int i=0;i<n;i++){
		int min =inf,u=-1;
		for(int v=0;v<n;v++){
			if(!vis[v]&&d[v]<min){
				min=d[v];
				u=v;
			}
		}
		if(u==-1) return ;
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(!vis[v]&&G[u][v]!=inf&&d[v]>d[u]+G[u][v]){
				d[v]=d[u]+G[u][v];
				pre[v].clear();
				pre[v].push_back(u);
				path[v].clear();
				path[v].push_back(u);
				num[v]=num[u];
				happy[v]=happy[u]+cost[v];
			}
			else if(!vis[v]&&G[u][v]!=inf&&d[v]==d[u]+G[u][v]){
				pre[v].push_back(u);
				num[v]+=num[u];
				if(happy[v]<happy[u]+cost[v]){
					happy[v]=happy[u]+cost[v];
					path[v].clear();
				    path[v].push_back(u);
				}
			}
		}
	}
}
void dfs(int ds){
	if(ds==0) return ;
    dfs(path[ds][0]);
	ans.push_back(ds);
}
int main(){
	cin>>n>>k>>st;
	Hash[st]=0,reHash[0]=st;
	for(int i=1;i<n;i++){
		cin>>c1>>cost[i];
		Hash[c1]=i,reHash[i]=c1;
		if(c1=="ROM") ds=i;//找到目的地
	}
	fill(G[0],G[0]+N*N,inf);
	for(int i=0;i<k;i++){
		cin>>c1>>c2>>dis;
		G[Hash[c1]][Hash[c2]]=G[Hash[c2]][Hash[c1]]=dis;
	}
	dijstra();
	dfs(ds);
	x=ans.size();
	printf("%d %d %d %d\n",num[ds],d[ds],happy[ds],happy[ds]/x);
	cout<<st;
	for(int i=0;i<ans.size();i++)
		cout<<"->"<<reHash[ans[i]];
	return 0;
}

#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_map>
using namespace std;
const int MAX = 200;
int dis[MAX], cost[MAX], pathCount[MAX], nodeCount[MAX];
int g[MAX][MAX], happiness[MAX], pre[MAX];
bool vis[MAX];
string city[MAX];
unordered_map<string, int> s2n;
int n, k;

void dfs(int s, int v)
{
    if (v == s)
    {
        cout << city[s];
        return;
    }
    dfs(s, pre[v]);
    cout << "->" << city[v];
}

void dijkstra()
{
    fill(dis, dis + MAX, INT_MAX);
    fill(pre, pre + MAX, -1);
    dis[0] = 0;
    happiness[0] = 0;
    pathCount[0] = 1;
    nodeCount[0] = 0;
    for (int i = 0; i < n; i++)
    {
        int MIN = INT_MAX, u = -1;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && dis[j] < MIN)
            {
                MIN = dis[j];
                u = j;
            }
        }
        vis[u] = true;
        for (int v = 0; v < n; v++)
        {
            if (!vis[v] && g[u][v])
            {
                if (dis[u] + g[u][v] < dis[v])
                {
                    dis[v] = dis[u] + g[u][v];
                    cost[v] = cost[u] + happiness[v];
                    pathCount[v] = pathCount[u];
                    nodeCount[v] = nodeCount[u] + 1;
                    pre[v] = u;
                }
                else if (dis[u] + g[u][v] == dis[v])
                {
                    pathCount[v] += pathCount[u];
                    if (cost[u] + happiness[v] > cost[v])
                    {
                        cost[v] = cost[u] + happiness[v];
                        nodeCount[v] = nodeCount[u] + 1;
                        pre[v] = u;
                    }
                    else if (cost[u] + happiness[v] == cost[v])
                    {
                        if (nodeCount[u] < nodeCount[v])
                        {
                            nodeCount[v] = nodeCount[u] + 1;
                            pre[v] = u;
                        }
                    }
                }
            }
        }
    }
    cout << pathCount[s2n["ROM"]] << " " << dis[s2n["ROM"]] << " " << cost[s2n["ROM"]] << " " << cost[s2n["ROM"]] / nodeCount[s2n["ROM"]] << endl;
    dfs(0, s2n["ROM"]);
}

int main()
{
    cin >> n >> k >> city[0];
    s2n[city[0]] = 0;
    for (int i = 1; i < n; i++)
    {
        cin >> city[i] >> happiness[i];
        s2n[city[i]] = i;
    }
    while (k--)
    {
        string u, v;
        int w;
        cin >> u >> v >> w;
        g[s2n[u]][s2n[v]] = g[s2n[v]][s2n[u]] = w;
    }
    dijkstra();
    return 0;
}