All Roads Lead to Rome（30）（MAP，DFS，模拟）（PAT甲级）

#include<bits/stdc++.h>
using namespace std;
map<string,int>city;
map<int,string>rcity;
map<int,vector<pair<int,int> > >edge;//对比string要比对比int慢很多，所以转换映射
int dis[207],path[207],hcount[207],happ[207],fstep[207],f[207];//源点到各点的最短距离，最短路径数量，快乐总数，快乐，经过点的个数，前一个点
int vis[207];
int main(){
    memset(dis,-1,sizeof(dis));
    memset(hcount,-1,sizeof(hcount));
    std::ios::sync_with_stdio(false);//关闭同步
    int n,k,i,d,s;
    string st,u,v;
    cin>>n>>k>>st;
    city[st]=0;//编号
    rcity[0]=st;//反编号
    happ[0]=0;
    dis[0]=0;
    hcount[0]=0;
    fstep[0]=0;
    path[0]=1;//init
    f[0]=0;
    for(i=1;i<n;++i){
        f[i]=i;
        cin>>u;
        rcity[i]=u;
        city[u]=i;
        cin>>happ[i];
    }
    for(i=0;i<k;++i){
        cin>>u>>v>>d;
        edge[city[u]].push_back(make_pair(city[v],d));
        edge[city[v]].push_back(make_pair(city[u],d));
    }
    s=0;
    vector<pair<int,int> >::iterator it;
    int next;
    while(s!=city["ROM"]){
        vis[s]=1;
        for(it=edge[s].begin();it!=edge[s].end();++it){
            next=it->first;
            if(dis[next]==-1||dis[next]>dis[s]+it->second){//松弛
                dis[next]=dis[s]+it->second;
                hcount[next]=hcount[s]+happ[next];
                path[next]=path[s];
                fstep[next]=fstep[s]+1;
                f[next]=s;
            }
            else{
                if(dis[next]==dis[s]+it->second){
                    path[next]+=path[s];
                    if(hcount[next]<hcount[s]+happ[next]){
                        hcount[next]=hcount[s]+happ[next];
                        fstep[next]=fstep[s]+1;
                        f[next]=s;
                    }
                    else{
                        if(hcount[next]==hcount[s]+happ[next]){
                            if(fstep[next]>fstep[s]+1){
                                fstep[next]=fstep[s]+1;
                                f[next]=s;
                            }
                        }
                    }
                }
            }
        }
        int mindis=-1,minnum;
        for(i=1;i<n;i++){
            if(dis[i]==-1)//如果当前边到不了初始点，直接pass
                continue;
            if(!vis[i]&&(mindis==-1||(dis[i]<mindis))){
                mindis=dis[i];
                minnum=i;
            }
        }
        s=minnum;//找到当前距离源点最近的一个点向下搜索
    }
    cout<<path[s]<<" "<<dis[s]<<" "<<hcount[s]<<" "<<hcount[s]/fstep[s]<<endl;
    int p=s;
    stack<int>ss;
    while(p){
        ss.push(p);
        p=f[p];
    }
    cout<<rcity[p];
    while(!ss.empty()){
        cout<<"->"<<rcity[ss.top()];
        ss.pop();
    }
    return 0;
}

All Roads Lead to Rome（30）（MAP，DFS，模拟）（PAT甲级）

原文：https://www.cnblogs.com/ldudxy/p/10821509.html