PAT (Advanced Level) 1087. All Roads Lead to Rome (30)

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<queue>

#include<string>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=+;

int n,m;

string st;

map<string ,int>m1;

map<int ,string>m2;

int sz;

int h[maxn];

struct Edge

{

    int u,v,c;

}e[maxn*maxn];

int tot;

vector<int>g[maxn];

int des;

int ans_cost=0x7FFFFFFF;

int ans_count=;

int ans_happy=;

int ans_point=;

int path[maxn],ans_path[maxn];

bool flag[maxn];

void dfs(int x,int cost,int happy,int point)

{

    if(cost>ans_cost) return;

    if(x==des)

    {

        if(cost<ans_cost)

        {

            ans_cost=cost;

            ans_count=;

            ans_happy=happy;

            ans_point=point;

            for(int i=;i<point;i++)

                ans_path[i]=path[i];

        }

        else if(cost==ans_cost)

        {

            ans_count++;

            if(happy>ans_happy)

            {

                ans_happy=happy;

                ans_point=point;

                for(int i=;i<point;i++)

                    ans_path[i]=path[i];

            }

            else if(happy==ans_happy)

            {

                if(point<ans_point)

                {

                    ans_point=point;

                    for(int i=;i<point;i++)

                        ans_path[i]=path[i];

                }

            }

        }

        return;

    }

    for(int i=;i<g[x].size();i++)

    {

        int id=g[x][i];

        path[point]=e[id].v;

        if(flag[e[id].v]==) continue;

        flag[e[id].v]=;

        dfs(e[id].v,cost+e[id].c,happy+h[e[id].v],point+);

        flag[e[id].v]=;

    }

}

int main()

{

    scanf("%d%d",&n,&m); cin>>st;

    m1[st]=++sz; m2[sz]=st;

    for(int i=;i<=n-;i++)

    {

        string name; cin>>name;

        m1[name]=++sz; m2[sz]=name;

        int val; scanf("%d",&val);

        h[sz]=val;

    }

    des=m1["ROM"];

    tot=;

    for(int i=;i<=m;i++)

    {

        string U,V; int c; cin>>U>>V>>c;

        e[tot++].u=m1[U]; e[tot].v=m1[V]; e[tot].c=c;

        g[m1[U]].push_back(tot);

        e[tot++].u=m1[V]; e[tot].v=m1[U]; e[tot].c=c;

        g[m1[V]].push_back(tot);

    }

    memset(flag,,sizeof flag);

    flag[]=;

    dfs(,,,);

    printf("%d %d %d %d\n",ans_count,ans_cost,ans_happy,ans_happy/ans_point);

    cout<<st;

    for(int i=;i<ans_point;i++)

        cout<<"->"<<m2[ans_path[i]];

    printf("\n");

    return ;

}