1. 原題： https://www.patest.cn/contests/pat-a-PRactise/1087

2. 思路：

3. 源碼：

#include<iostream>#include<map>#include<string>using namespace std;const int Max = 200 + 5;//最大結(jié)點(diǎn)數(shù)const int INF = 0x7FFFFFFF;//表示無窮大int G[Max][Max];//圖的鄰接矩陣表示法int collect[Max] = { 0 };//記錄某點(diǎn)是否被收錄int path[Max];//存儲最短路徑上的結(jié)點(diǎn)號int dist[Max];//到某點(diǎn)的最短路徑長度int happy[Max] = { 0 };//記錄每個點(diǎn)的幸福指數(shù)int sum_happy[Max] = { 0 };//最短路徑上的總指數(shù)int route[Max] = { 0 };//到某點(diǎn)的路徑條數(shù)int cnt[Max] = { 0 };//記錄到某點(diǎn)的路徑上的點(diǎn)數(shù)，不含起點(diǎn)int N, K;//分別為結(jié)點(diǎn)數(shù)， 路徑數(shù)map<string, int> id;//字符串映射成數(shù)字map<int, string> name;//數(shù)字映射成字符串int findMin();//找出未收錄的最小權(quán)值void dijkstra(int start);//dijkstra經(jīng)典算法void print(int num);//遞歸逆序打印路徑int main(void){	//freopen("in.txt", "r", stdin);	string s, d;//起點(diǎn)，終點(diǎn)	cin >> N >> K >> s;	id[s] = 0;//起點(diǎn)映射為0	name[0] = s;	for (int i = 0; i < N; i++)//圖的初始化	{		for (int j = 0; j < N; j++)			G[i][j] = INF;		path[i] = -1;	}	for (int i = 1; i < N; i++)//讀入數(shù)據(jù)	{		int val;//幸福指數(shù)		cin >> s >> val;		id[s] = i;		name[i] = s;		happy[i] = val;	}	for (int i = 0; i < K; i++)	{		int wgt;//權(quán)值		cin >> s >> d >> wgt;		int s1, d1;		s1 = id[s];		d1 = id[d];		G[s1][d1] = G[d1][s1] = wgt;	}	dijkstra(0);//最短路經(jīng)典算法	int end = id["ROM"];//終點(diǎn)	printf("%d %d %d %d/n", route[end], dist[end], sum_happy[end],		sum_happy[end] / (cnt[end] + 1));//分別為最短路的路徑數(shù)， 路徑長度，總指數(shù)，平均指數(shù)	print(end);//打印路徑	cout << endl;	return 0;}int findMin()//找出未收錄的最小權(quán)值{	int min_id = -1;	int min_val = INF;	for (int i = 0; i < N; i++)	{		if (collect[i] == 0 && dist[i] < min_val)		{			min_val = dist[i];			min_id = i;		}	}	return min_id;}void dijkstra(int start)//dijkstra經(jīng)典算法{	for (int i = 0; i < N; i++)//初始化	{		dist[i] = G[start][i];		sum_happy[i] = happy[i];	}	route[start] = 1;//起點(diǎn)的路徑條數(shù)初始為1, 0不可以。	dist[start] = 0;//起點(diǎn)到起點(diǎn)為0	while (1)	{		int v = findMin();		if (v == -1)//循環(huán)終止			break;		collect[v] = 1;		for (int w = 0; w < N; w++)		{			if (collect[w] == 0 && G[v][w] < INF)			{				if ((dist[v] + G[v][w]) < dist[w])//找到最短路				{					cnt[w] = cnt[v] + 1;//到w的路徑上的結(jié)點(diǎn)數(shù)加1					dist[w] = dist[v] + G[v][w];					route[w] = route[v];//更新路徑條數(shù)					sum_happy[w] = sum_happy[v] + happy[w];					path[w] = v;//表示到w的上一個結(jié)點(diǎn)是v				}				else if ((dist[v] + G[v][w]) == dist[w])//存在多個最短路				{					route[w] += route[v];//更新路徑條數(shù)					if (sum_happy[w] < (sum_happy[v] + happy[w]))//存在最大幸福指數(shù)的路徑					{						path[w] = v;						cnt[w] = cnt[v] + 1;						sum_happy[w] = sum_happy[v] + happy[w];					}					else if ((sum_happy[w] == sum_happy[v] + happy[w])						&& (cnt[w] > (cnt[v] + 1)))//存在最大的平均指數(shù)的路徑					{						path[w] = w;						cnt[w] = cnt[v] + 1;					}				}			}			}	}	return;}void print(int num)//遞歸逆序打印路徑{	if (num == -1)//遞歸結(jié)束條件	{		cout << name[0];		return;	}	print(path[num]);	cout << "->" << name[num];}