1087 All Roads Lead to Rome （30

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<string>
#include<map>
using namespace std;

const int MAXV = 210;
const int INF = 1000000000;

int n, m, st = 0, G[MAXV][MAXV], weight[MAXV];
int d[MAXV], numPath = 0, maxW = 0;
double maxAvg = 0;
bool vis[MAXV];
vector<int> pre[MAXV];
vector<int> tempPath, path;
map<string, int> city2index;
map<int, string> index2city;

void Dijkstra(int s)//s 为源点
{
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++)//外层循环次数确保正确
    {
        //取V-S集合的最小距离点
        int u = -1, min = INF;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && d[j] < min)
            {
                min = d[j];
                u = j;
            }
        }
        if (u == -1) return;//s与剩余节点不连通
        vis[u] = true;
        for (int v = 0; v < n; v++)
        {
            if (vis[v] == false && 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);
                }
            }
        }
    }
}
void DFS(int v)
{
    if (v == st)
    {
        numPath++;//叶子节点数即路径数
        tempPath.push_back(v);
        double tempAvg = 0;
        int tempWeight = 0;
        for (int i = 0; i < tempPath.size(); i++)
        {
            tempWeight += weight[tempPath[i]];
        }
        tempAvg = tempWeight * 1.0 / (tempPath.size() - 1);
        if (tempWeight > maxW)
        {
            maxW = tempWeight;
            maxAvg = tempAvg;
            path = tempPath;
        }
        else if (tempWeight == maxW && tempAvg > maxAvg)
        {
            maxAvg = tempAvg;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++)
    {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}
int main()  
{
    fill(G[0], G[0] + MAXV * MAXV, INF);
    scanf("%d%d", &n, &m);
    string city;
    cin >> city;
    city2index[city] = 0;
    index2city[0] = city;
    for (int i = 1; i < n; i++)
    {
        cin >> city >> weight[i];
        city2index[city] = i;
        index2city[i] = city;
    }
    string start, dest;
    for (int i = 0; i < m; i++)
    {
        cin >> start >> dest;
        cin >> G[city2index[start]][city2index[dest]];
        G[city2index[dest]][city2index[start]] = G[city2index[start]][city2index[dest]];
    }
    Dijkstra(0);//单源
    DFS(city2index["ROM"]);
    cout << numPath << ' ' << d[city2index["ROM"]] << ' ' << maxW << ' ' << int(maxAvg) << endl;
    for (int i = path.size() - 1; i >= 0; i--)
    {
        cout << index2city[path[i]];
        if(i!=0)
            cout << "->";
    }
    system("pause");
    return 0;
}