1087 All Roads Lead to Rome

题目大意

有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为快乐值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出快乐值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径.

思路解析

仍然是dijkstra + dfs，加上这次已经考察了3次了，如果还不会就要反思一下了。

示例代码

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#define INF (~(0x1<<31))
using namespace std;
int gra[210][210];
vector<int> hap(210);
vector<vector<int>> path(210);
map<string, int> mapp;
map<int, string> rmapp;
int maxsum = 0, pathnum = 0;
double aver = 0;
vector<int> res,tempath;
void dfs(int v,int sum,int num) {//sum快乐和  num节点数
	sum += hap[v];
	num++;
	tempath.push_back(v);
	if (v == 0) {//回到起点了
		pathnum++;
		if (sum > maxsum) {//原来我不是真的快乐
			maxsum = sum;
			res = tempath;
			aver = sum*1.0 / num;
		}
		else if (sum == maxsum && sum*1.0 / num > aver) {
			res = tempath;
			aver = sum*1.0 / num;
		}
		tempath.pop_back();
		return;
	}
	for (int i = 0; i < path[v].size(); i++) {
		dfs(path[v][i], sum , num);
	}
	tempath.pop_back();
}
int main() {
	int n, k, temp;
	string name;
	cin >> n >> k >> name;
	mapp[name] = 0;
	rmapp[0] = name;
	fill(gra[0], gra[0] + 210 * 210, INF);
	hap[0] = 0;
	for (int i = 1; i < n; i++) {
		cin >> name >> temp;
		mapp[name] = i;
		rmapp[i] = name;
		hap[i] = temp;
	}
	for (int i = 0; i < k; i++) {
		string s1, s2;
		int c;
		cin >> s1 >> s2 >> c;
		int a = mapp[s1];
		int b = mapp[s2];
		gra[a][b] = gra[b][a] = c;
	}
	vector<int> dist(n,INF);
	vector<bool> visited(n);
	dist[0] = 0;
	for (int i = 0; i < n; i++) {
		int min = INF, u;
		for (int j = 0; j < n; j++) {
			if (!visited[j] && dist[j] < min) {
				min = dist[j];
				u = j;
			}
		}
		visited[u] = true;
		for (int j = 0; j < n; j++) {
			if (!visited[j] && gra[u][j] != INF) {
				if (dist[u] + gra[u][j] < dist[j]) {
					dist[j] = dist[u] + gra[u][j];
					path[j].clear();
					path[j].push_back(u);
				}
				else if (dist[u] + gra[u][j] == dist[j]) {
					path[j].push_back(u);
				}
			}
		}
	}
	int end = mapp["ROM"];
	dfs(end,0,-1);
	cout << pathnum << " " << dist[end] << " " << maxsum << " " << (int)aver << endl;
	cout << rmapp[res[res.size()-1]];
	for (int i = res.size()-2; i >= 0; i--) {
		cout << "->" << rmapp[res[i]];
	}
	return 0;
}