（单源最短路径；多尺标；记录路径条数）
题目大意
从一个城市出发有多条路到达“ROM”，求最佳路径。首先选择最短路径；若最短路径相同，选择幸福指数最大的；若还相同，选择平均幸福指数最大的（平均不包括起点，因为起点没有幸福指数）。同时还要在第一行输出最短路径条数、路径长度、幸福指数、平均幸福指数；第二行输出最佳路径。
思路
Dijkstra算法。dis[]存放最短路径长度；nowgethappy[]存放当前幸福指数。用一个数组point存路径经过的顶点数，point[i]表示从起点到结点i的最佳路径经过几个结点。用一个数组num存最短路径条数，当新路径比当前最短路径短时，num[v]=num[u]+Adj[u][i].w;; 当num[v]==num[u]+Adj[u][i].wnum[i]时，将u的最短路径条数累加到v上，即num[v]=num[v]+num[u];。数组pre[i]表示最短路径中结点i的前驱，最后递归输出路径。 建立了一个int到string的map和一个string到int的map，将名字和编号对应起来。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
#define MAX 205
#define INF 100000000
struct node {
int v, w;
};
int n, m, ren = 0, s;
vector<node>Adj[MAX];
map<int, string>idtoname;
map<string, int>nametoid;
int happiness[MAX], dis[MAX], nowgethappy[MAX] = { 0 }, point[MAX] = { 0 }, pre[MAX], num[MAX] = { 0 };
bool vis[MAX] = { false };
int addid(string a) {
int id = ren;
ren++;
idtoname[id] = a;
nametoid[a] = id;
return id;
}
int Dijkstra(int s) {
int i, j;
fill(dis, dis + n, INF);
for (i = 0;i < n;i++)pre[i] = i;
dis[s] = 0;
num[s] = 1;
for (i = 0;i < n;i++) {
int min = INF, u = -1;
for (j = 0;j < n;j++) {
if (vis[j] == false && dis[j] < min) {
min = dis[j];
u = j;
}
}
if (u == -1)return -1;
vis[u] = true;
for (j = 0;j < Adj[u].size();j++) {
int v = Adj[u][j].v;
if (vis[v] == false) {
if (dis[v] > dis[u] + Adj[u][j].w) {
nowgethappy[v] = nowgethappy[u] + happiness[v];
dis[v] = dis[u] + Adj[u][j].w;
point[v] = point[u] + 1;
num[v] = num[u];
pre[v] = u;
}
else if (dis[v] == dis[u] + Adj[u][j].w) {
num[v] = num[v] + num[u];//注意这里是把num[u]累加到num[v]上。
if (nowgethappy[v] < nowgethappy[u] + happiness[v]) {
nowgethappy[v] = nowgethappy[u] + happiness[v];
point[v] = point[u] + 1;
pre[v] = u;
}
else if (nowgethappy[v] == nowgethappy[u] + happiness[v]) {
if (point[v] > point[u] + 1) {
point[v] = point[u] + 1;
pre[v] = u;
}
}
}
}
}
}
}
void DFS(int x) {
if (x == s) {
cout << idtoname[x];
return;
}
DFS(pre[x]);
cout << "->" << idtoname[x];
}
int main() {
int i, happy;
scanf("%d%d", &n,&m);
string start;
cin >> start;
s = addid(start);
for (i = 1;i < n;i++) {
string temp;
cin >> temp;
scanf("%d", &happy);
int id = addid(temp);
happiness[id] = happy;
}
for (i = 0;i < m;i++) {
string temp1, temp2;
cin >> temp1 >> temp2;
node tempn;
scanf("%d", &tempn.w);
int id1 = nametoid[temp1], id2 = nametoid[temp2];
tempn.v = id2;Adj[id1].push_back(tempn);
tempn.v = id1;Adj[id2].push_back(tempn);
}
Dijkstra(s);
int ending = nametoid["ROM"];
printf("%d %d %d %d\n", num[ending], dis[ending], nowgethappy[ending], nowgethappy[ending] / (point[ending]));
DFS(ending);
return 0;
}
