这里只说明关键部分。
有三个优先级，由高到低分别是：
距离、高兴值、平均高兴值。
距离即是最普通的Dijkstra所求的目标。
高兴值是点权变体之一。
平均高兴值可化为求最短路径中的最少结点路径，也属于点权变体之一。
在更新结果的代码中，优先级高的更新的结果要更多。
所有优先级低的更新时必须保证比它更高优先级的结果是一致的。
下面放代码：（PS，怎么感觉最近这么多Dijkstra。。。）
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<map> using namespace std; map<string, int> str2int; map<int, string> int2str; const int M = 210; const int INF = INT32_MAX; int n, e, G[M][M], vertex[M]; int num[M], path[M], dist[M],happy[M],node[M]; bool vis[M]; string start; int cur = -1; int change(string city) { if (str2int.find(city) != str2int.end()) { return str2int[city]; } cur++; str2int[city] = cur; int2str[cur] = city; return cur; } void initGraph() { fill(G[0],G[0]+M*M,INF); cin >> n >> e>>start; string c1, c2; int idc1, idc2, ele; vertex[change(start)] = 0; for (int i = 0; i < n-1; i++) { cin >> c1 >> ele; vertex[change(c1)]=ele; } for (int i = 0; i < e; i++) { cin >> c1 >> c2 >> ele; idc1 = change(c1); idc2 = change(c2); G[idc1][idc2] = G[idc2][idc1] = ele; } } void Dijkstra() { fill(dist,dist+n,INF); for (int i = 1; i < n; i++) { path[i] = i; } int s = str2int[start]; dist[s] = 0; num[s] = 1; int k, m; for (int i = 0; i < n; i++) { k = -1, m = INF; for (int j = 0; j < n; j++) { if (!vis[j] && dist[j]<m) { m = dist[j]; k = j; } } if (k==-1) { return; } else { vis[k] = true; } for (int j = 0; j < n; j++) { if (!vis[j] && G[k][j]!=INF) { if (dist[k]+G[k][j]<dist[j]) { dist[j] = dist[k] + G[k][j]; path[j] = k; num[j] = num[k]; happy[j] = happy[k] + vertex[j]; node[j] = node[k]+1; } else if (dist[k] + G[k][j] == dist[j]) { num[j] += num[k]; if (happy[k]+vertex[j]>happy[j]) { happy[j] = happy[k] + vertex[j]; node[j] = node[k] + 1; path[j] = k; } else if (happy[k] + vertex[j] == happy[j] && node[j] > node[k] + 1) { node[j] = node[k] + 1; path[j] = k; } } } } } } void printPath(int s,int d,string &r) { if (s==d) { r.append(int2str[d]); r.append("->"); return; } printPath(s,path[d],r); r.append(int2str[d]); r.append("->"); } int main() { initGraph(); Dijkstra(); int s = str2int[start]; int d = str2int["ROM"]; cout << num[d] <<" "<< dist[d]<<" "<<happy[d]<<" "<<happy[d]/node[d]<<endl; string r; printPath(s,d,r); cout << r.substr(0,r.size()-2); int a = 0; return 0; }
