A1087.md

A1087 All Roads Lead to Rome

1.题意理解

俺们要上罗马去旅行，想让旅行路程最短，但是玩的又最开心。

2.思路分析

题目给出的输入是字符串，要哈希为整数，最简单的哈希方法就是在输入点权（每个城市的幸福感）时逐个计数。

使用dijkstra来计算最短路。

dfs搜索使得幸福感最高的路径，如果幸福感相同，要使平均幸福感最高。

3.参考代码

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

const int N = 256, INF = 0x3f3f3f3f;
int G[N][N], d[N], happiness[N];
bool vis[N] = {false};
int n, k, st, ed;
unordered_map<int, string> i2s;
unordered_map<string, int> s2i;
vector<int> pre[N], path, temp_path;

void dijkstra(int s)
{
    fill(d, d + N, 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] && 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] && G[u][v] != INF)
                if (d[u] + G[u][v] < d[v])
                {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v])
                    pre[v].push_back(u);
    }
}

int max_hap = 0, cnt = 0;
double max_avg_hap = 0.0;
string start;
void dfs(int v)
{
    if (v == st)
    {
        cnt++;
        temp_path.push_back(v);
        int hap = 0;
        for (int i = 0; i < temp_path.size() - 1; i++)
        {
            int id = temp_path[i];
            hap += happiness[id];
        }
        double avg_hap = 1.0 * hap / (temp_path.size() - 1);
        if (hap > max_hap)
        {
            path = temp_path;
            max_hap = hap;
            max_avg_hap = avg_hap;
        }
        else if (hap == max_hap && avg_hap > max_avg_hap)
        {
            path = temp_path;
            max_avg_hap = avg_hap;
        }
        temp_path.pop_back();
        return;
    }
    temp_path.push_back(v);
    for (int it : pre[v])
        dfs(it);
    temp_path.pop_back();
}

int main()
{
    fill(G[0], G[0] + N * N, INF);
    scanf("%d%d", &n, &k);
    cin >> start;
    s2i[start] = n - 1;
    i2s[n - 1] = start;
    int h, cost;
    string city, c1, c2;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> city >> h;
        s2i[city] = i;
        i2s[i] = city;
        happiness[i] = h;
    }
    for (int i = 0; i < k; i++)
    {
        cin >> c1 >> c2 >> cost;
        int id1 = s2i[c1], id2 = s2i[c2];
        G[id1][id2] = G[id2][id1] = cost;
    }
    st = s2i[start], ed = s2i["ROM"];
    dijkstra(st);
    dfs(ed);
    printf("%d %d %d %d\n", cnt, d[ed], max_hap, (int)max_avg_hap);
    for (int i = path.size() - 1; i >= 0; i--)
    {
        cout << i2s[path[i]];
        if (i > 0)
            cout << "->";
        else
            cout << endl;
    }
    system("pause");
    return 0;
}