条条大路通罗马

标签：resxingfu int 条条大路通罗马 start2 cost mp countz

https://www.acwing.com/problem/content/1579/

思路：
最短路里面的经典题型，在最短路的时候维护多个变量。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int N = 250; 
unordered_map<string, int> mp; //对字符串离散化
string re_map[N]; //建立一个反映射
int cost[N][N], w[N]; //cost记录花费，w记录达到每个城市可以获得的幸福指数
int pre[N];
int resxingfu[N];
int sum[N];
int d[N];
bool st[N];
int countz[N];
int n, k;
string start,dest;
int cnt = 1;


void dijk(int start2)
{
    memset(d, 0x3f, sizeof d);
    d[start2] = 0;
    resxingfu[start2] = 0;
    sum[start2] = 1;
    for (int i = 0; i <n; i++)
    {
        int t = -1;
        for (int j = 1; j <=n; j++)
        {
            if (!st[j] && (t == -1 || d[t]>d[j]))
            {
                t = j;
            }
        }

        st[t] = true;
        for (int j = 1; j <=n; j++)
        {
            if (d[j] >d[t] + cost[t][j])
            {
                    d[j] = d[t] + cost[t][j];
                    pre[j] = t;
                    sum[j] = sum[t];
                    countz[j] = countz[t] + 1;
                    resxingfu[j] = resxingfu[t] + w[j];
            }
            else if (d[j] ==d[t] + cost[t][j])
            {
                sum[j] += sum[t];
                if (resxingfu[j] < resxingfu[t] + w[j])
                {
                    resxingfu[j] = resxingfu[t] + w[j];
                    countz[j]=countz[t] + 1;
                    pre[j] = t;
                }
                else if (resxingfu[j] == resxingfu[t] + w[j])
                {
                    if (countz[j] - 1 > countz[t])
                    {
                        pre[j] = t;
                        countz[j] =countz[t]+1;
                    }
                }
            }
        }
    }
}

int main()
{
    cin >> n >> k >> start;
    memset(cost, 0x3f, sizeof cost);
    dest= "ROM";
    mp[start] = cnt;
    re_map[cnt] = start;
    cnt++;
    for (int i = 1; i <= n-1; i++)
    {
        string a;
        int b;
        cin >> a >> b;
        if (!mp.count(a)) mp[a] = cnt, re_map[cnt] = a, cnt++;
        w[mp[a]] = b;
    }

    for (int i = 1; i <= k; i++)
    {
        string a, b;
        int spend;
        cin >> a >> b >> spend;
        int aa = mp[a], bb = mp[b];
        cost[aa][bb] = cost[bb][aa] = min(cost[aa][bb],spend);
    }

    int start2 = mp[start];
    int dest2 = mp[dest];
    dijk(start2);
    vector<int> res;
    for (int i = dest2; i != start2; i = pre[i])
    {
        res.push_back(i);
    }
    res.push_back(start2);

    cout << sum[dest2] << " " << d[dest2] << " " << resxingfu[dest2] << " " << resxingfu[dest2] / (res.size() - 1) << endl;
    cout << re_map[res[res.size() - 1]];
    for (int i = res.size() - 2; i >= 0; i--)
    {
        cout << "->" << re_map[res[i]];
    }
    return 0;
}

标签：resxingfu,int,条条大路通罗马,start2,cost,mp,countz
From： https://www.cnblogs.com/xjtfate/p/16610719.html