All Roads Lead to Rome（30）（MAP【int，string】，邻接表，DFS，模拟，SPFA）（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;
}

/*#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 ;
typedef struct node{
    int v;//节点编号
    int cost;//边权值
};
int N;//城市数量
int K;//道路条数
string start;//起始点城市名字
int happy[207];//存放各个城市的快乐值
map<string,int>stringToInt;//城市名字->编号
map<int,string>intToString;//编号->城市名字
vector<node>graph[207];//邻接表
int d[207];//记录从起始城市到达点i的最少花费值
vector<int>pre[207];//记录前一个节点
vector<int>path,tempPath;
int optHappy=0;
double optAverageHappy=0;
int cnt=0;//记录最短路径条数
int inq[207];//记录节点是否在队列中
void spfa(int s){
    for(int i=0;i<N;++i)
        d[i]=INF;
    d[s]=0;
    queue<int>q;
    q.push(s);
    inq[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int j=0;j<graph[u].size();++j){
            int v=graph[u][j].v;
            int cost=graph[u][j].cost;
            if(!v)
                continue;
            if(d[u]+cost<d[v]){
                d[v]=d[u]+cost;
                pre[v].clear();
                pre[v].push_back(u);
                if(!inq[v]){
                    q.push(v);
                    inq[v]=1;
                }
            }
            else if(d[u]+cost==d[v])
                pre[v].push_back(u);
        }
    }
}
void dfs(int nowVisit){
    if(!nowVisit){
        cnt++;
        tempPath.push_back(nowVisit);
        int happyValue=0;
        for(int i=tempPath.size()-2;i>=0;--i)
            happyValue+= happy[tempPath[i]];
        double averageHappyValue=1.0*happyValue/(tempPath.size()-1);
        if(happyValue>optHappy){
            optHappy=happyValue;
            optAverageHappy=averageHappyValue;
            path=tempPath;
        }
        else if(happyValue==optHappy&&averageHappyValue>optAverageHappy){
            optAverageHappy=averageHappyValue;
            path=tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(nowVisit);
    for(auto&it:pre[nowVisit])
  dfs(it);
    tempPath.pop_back();
}
int main(){
    std::ios::sync_with_stdio(false);//关闭同步
    cin>>N>>K>>start;
    stringToInt[start]=0; //起始城市编号为0
    intToString[0]=start;
    string city;
    int happyness;
    for(int i=1;i<N;++i){
        cin>>city>>happyness;
        stringToInt[city]=i;
        intToString[i]=city;
        happy[i]=happyness;
    }
    string city1,city2;
    int cost;
    for(int i=0;i<K;++i){
        cin>>city1>>city2>>cost;
        int id1=stringToInt[city1];
        int id2=stringToInt[city2];
        node x,y;
        x.v=id2;
        x.cost=cost;
        y.v=id1;
        y.cost=cost;
        graph[id1].push_back(x);
        graph[id2].push_back(y);
    }
    int destination=stringToInt["ROM"];
    spfa(0);
    dfs(destination);
    cout<<cnt<<" "<<d[destination]<<" "<<optHappy<<" "<<(int)optAverageHappy<<endl;
    for(int i=path.size()-1;i>=0;--i) {
        cout<<intToString[path[i]];
        if(i)
            cout<<"->";
    }
    return 0;
}*/

//SPFA先处理再DFS

巴特西

All Roads Lead to Rome（30）（MAP【int，string】，邻接表，DFS，模拟，SPFA）（PAT甲级）

最新文章

热门文章