PAT甲1087 All Roads Lead to Rome（30 分）

#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;

const int inf=;
int G[][],d[],happy[];
vector<int> pre[];
bool vis[];
int N,K,st,ed;

map<string,int> mp1;
map<int,string> mp2;

void Dij(int st)
{
    fill(d,d+,inf);
    memset(vis,false,sizeof(vis));
    d[st]=;
    for(int i=;i<N;i++)
    {
        int u=-,MIN=inf;
        for(int j=;j<N;j++)
        {
            if(vis[j]==false&&d[j]<MIN)
            {
                MIN=d[j];
                u=j;
            }
        }
        if(u==-)return ;
        vis[u]=true;
        for(int v=;v<N;v++)
        {
            if(G[u][v]<inf&&vis[v]==false)
            {
                if(d[u]+G[u][v]<d[v])
                {
                    pre[v].clear();
                    pre[v].push_back(u);
                    d[v]=d[u]+G[u][v];
                }
                else if(d[u]+G[u][v]==d[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }
}


int maxh=-,nump=;
double maxAvg=-;
vector<int> path,temppath;
void DFS(int now)
{
    if(now==st)
    {
        nump++;
        temppath.push_back(now);
        int temph=;
        for(int i=;i<temppath.size()-;i++)
        {
            temph+=happy[temppath[i]];
        }
        double avg=*temph/(temppath.size()-);
        if(temph>maxh)
        {
            path=temppath;
            maxh=temph;
            maxAvg=avg;
        }
        else if(temph==maxh&&avg>maxAvg)
        {
            path=temppath;
            maxAvg=avg;
        }
        temppath.pop_back();
        return;
    }
    temppath.push_back(now);
    for(int i=;i<pre[now].size();i++)
    {
        DFS(pre[now][i]);
    }
    temppath.pop_back();
}

int main()
{
    fill(G[],G[]+*,inf);
    char city[];
    int num=;
    scanf("%d %d %s",&N,&K,&city);
    if(mp1.find(city)==mp1.end())
    {
        mp1[city]=num;
        mp2[num]=city;
        st=num;
        num++;
    }
    for(int i=;i<N-;i++)
    {
        scanf("%s",&city);
        if(mp1.find(city)==mp1.end())
        {
            mp1[city]=num;
            mp2[num]=city;
            num++;
        }
        if(strcmp(city,"ROM")==)
        {
            ed=mp1[city];
        }
        scanf("%d", &happy[mp1[city]]);
    }
    for(int i=;i<K;i++)
    {
        char c1[],c2[];
        int dis;
        scanf("%s %s %d",&c1,&c2,&dis);
        int p1=mp1[c1];
        int p2=mp1[c2];
        G[p1][p2]=dis;
        G[p2][p1]=dis;
    }
    Dij(st);
    DFS(ed);
    printf("%d %d %d %d\n",nump,d[ed],maxh,(int)maxAvg);
    for(int i=path.size()-;i>=;i--)
    {
        if(i!=path.size()-)printf("->");
        cout<<mp2[path[i]];
    }
    return ;
}