PAT甲级1087.

目录

A1087

题目

样例

输入:

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

输出:

3 3 195 97
HZH->PRS->ROM

思路和坑点

　　由于，对于最短路径的优化条件比较复杂，还需要统计最短路径条数，因此，使用Dijksatra+dfs的方法得到所求的最短路径，其中Dijkstra算法用于获得多条备选路径，dfs对每一条路径进行遍历，然后根据优化尺度比较最终保留符合条件的路径，并输出。
　　要点:
　　其中，需要吧所有的城市结点映射成为0~n-1，其中由于起点城市没有happy值，所以不妨直接令起点映射为0，并且happy值为0，方便之后的统计计算。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXV 205
#define INF 0x3fffffff
int n,k;                            //图的顶点个数，图的边个数 
int cnt=0;                          //记录路径条数 
int totalh=-1;                      //第二优化尺度（总的happy值） 
int happy[MAXV];                    //happy映射 
int G[MAXV][MAXV];                  //图 
int dis[MAXV];                      //最短距离数组 
bool vis[MAXV]={false};             //访问标记 

string st,ed="ROM";                 //起始和结束 

vector<int> path[MAXV];             //多路径记录 
vector<int> pathout,temppath;       //输出路径和临时路径存放 

unordered_map<string,int> mp;       //城市的下标映射
unordered_map<int,string> mpi;

void D();                           //Dijkstra算法 
void DFS(int v); 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    fill(G[0],G[0]+MAXV*MAXV,INF);
    scanf("%d%d",&n,&k);
    cin>>st;                     
    mp[st]=0;                       //起始点映射为0    
    mpi[0]=st;
    happy[0]=0;                     //起始点的happy为0 
    for(int i=1;i<n;i++){           //读入happy并完成坐标映射 
        string temp;
        cin>>temp>>happy[i];
        mp[temp]=i;mpi[i]=temp;
    }
    for(int i=0;i<k;i++){           //读入边 
        string c1,c2;
        int ct1,ct2,c;
        cin>>c1>>c2>>c;
        ct1=mp[c1];ct2=mp[c2];
        G[ct1][ct2]=G[ct2][ct1]=c;
    }
    
    int edn=mp[ed];                 //终点下标 
    D();
    DFS(edn);
    int avh=totalh/(pathout.size()-1);
    cout<<cnt<<' '<<dis[edn]<<' '<<totalh<<' '<<avh<<'\n';
    for(int i=pathout.size()-1;i>=0;i--){
        int k=pathout[i];
        if(i!=pathout.size()-1)    printf("->");
        cout<<mpi[k];
    } 
    return 0;    
}
void D(){
    fill(dis,dis+MAXV,INF);
    dis[0]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(dis[u]+G[u][v]<dis[v]){
                    dis[v]=dis[u]+G[u][v];
                    path[v].clear();
                    path[v].push_back(u); 
                }
                else if(dis[u]+G[u][v]==dis[v]){
                    path[v].push_back(u);
                }
            }
        }
    }
}
void DFS(int v){
    if(v==0){                           //当获得一条路径时 
        cnt++;                          //路径计数器加一 
        temppath.push_back(0);
        int value=0;                    //计算当前获得路径的happy值 
        for(int i=0;i<temppath.size();i++){
            int k=temppath[i];
            value+=happy[k];
        }
        if(value>totalh){               //如果happy更多，则更新 
            totalh=value;
            pathout=temppath;
        }
        else if(value==totalh&&temppath.size()<pathout.size()){    //如果happy相同，城市个数少的平均happy更高，则更新 
            pathout=temppath;
        }
        temppath.pop_back();
        return;
    }
    temppath.push_back(v);
    for(int i=0;i<path[v].size();i++){
        DFS(path[v][i]);
    } 
    temppath.pop_back();
}