PAT_甲级_1087 All Roads Lead to Rome (30point(s)) (C++)【Dijkstra/DFS】

目录

​​1，题目描述​​

​​题目描述​​

​​输入​​

​​输出​​

​​2，思路​​

​​数据结构​​

​​算法 ​​

​​3，AC代码​​

​​4，解题过程​​

1，题目描述

Sample Input:

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      

Sample Output:

3 3 195 97
HZH->PRS->ROM      

题目描述

条条大路通罗马。计算从起点到ROM的最短路径（花费最少），若不唯一，则取可以获得最大幸福度的路径，若仍不唯一，则取平均幸福度最大的一条。

输入

1. 第一行：城市数目N，路的数目K，起始点；
2. N-1行：（除了起点）城市的幸福指数；
3. K行：每条路的两端及花费；

输出

1. 第一行：最少花费路径数目，最少花费，幸福总值，幸福平均值；
2. 第二行：最短路径；

2，思路

Dijkstra+DFS，似曾相识有木有​​@&再见萤火虫&【PAT_甲级_1030 Travel Plan (30分) (C++)【Dijkstra/DFS】】​​

数据结构

• map<string, int> sTOi：城市到数字映射；
• map<int, string> iTOs：数字到城市映射；
• int happiness[201]：每个城市的幸福指数；
• int graph[201][201]：邻接矩阵表示图 存放路的权值（cost）；
• vector<int> pre[201]：所有最短路径（以前驱节点的形式表示）；
• vector<int> path, tem：path最短路径 tem暂存路径；
• int dis[201]：起点到各个城市的最短距离；

算法 

1. 将城市代表的字符串，一一用数字表示（用两个map实现）：



2. Dijkstra求出从起点到达每个城市的最短路径pre：



3. DFS遍历起点到终点的所有最短路径（由于pre存放的是每个节点的前驱，所以遍历时，从终点des开始），更新最短路径pre，最大幸福值，最短路径数目ways：

3，AC代码

 （带感叹号的是容易出错的地方。）

#include<bits/stdc++.h>
using namespace std;
int N, K, des;              //N城市数目 K路的数目 des终点编号
map<string, int> sTOi;      //城市到数字映射
map<int, string> iTOs;      //数字到城市映射
int happiness[201];         //每个城市的幸福指数
int graph[201][201];        //邻接矩阵表示图 存放路的权值（cost）
vector<int> pre[201];       //所有最短路径
vector<int> path, tem;      //path最短路径 tem暂存路径
bool visited[201];
int dis[201];               //起点到各个城市的最短距离

int ways = 0, minCost = INT_MAX, maxHap = 0, aveHap;    //ways最短路总数 minCost最小花费 maxHap最大快乐值 aveHap平均快乐值
void dfs(int start, int hap){
    tem.push_back(start);
    if(start == 0){
        ways++;
        if(hap > maxHap){
            maxHap = hap;
            path = tem;
        }else if(hap == maxHap){
            if(tem.size() < path.size())    //平均值大的
                path = tem;
        }
    }
    for(int i = 0; i < pre[start].size(); i++){
        dfs(pre[start][i], hap + happiness[pre[start][i]]);    //！！！
    }
    tem.pop_back();
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE

    string city1, city2;
    int id1, id2, num;
    city1.resize(3);
    city2.resize(3);
    scanf("%d %d %s", &N, &K, &city1[0]);    //！！！
    sTOi[city1] = 0;
    iTOs[0] = city1;
    happiness[0] = 0;
    for(int i = 1; i < N; i++){
        scanf("%s %d", &city1[0], &num);     //！！！
        if(city1 == "ROM") des = i;
        sTOi[city1] = i;
        iTOs[i] = city1;
        happiness[i] = num;
    }
    fill(graph[0], graph[0] + 201 * 201, INT_MAX);
    for(int i = 0; i < K; i++){
        scanf("%s %s %d", &city1[0], &city2[0], &num);
        id1 = sTOi[city1];
        id2 = sTOi[city2];
        graph[id1][id2] = graph[id2][id1] = num;
    }
    fill(dis, dis + 201, INT_MAX);

    dis[0] = 0;
    for(int i = 0; i < N; i++){
        int u = -1;
        int minDis = INT_MAX;
        for(int j = 0; j < N; j++){            //！！！
            if(!visited[j] && dis[j] < minDis){
                u = j;
                minDis = dis[j];
            }
        }
        if(u == -1) break;
        visited[u] = true;
        for(int v = 0; v < N; v++){
            if(!visited[v] && graph[u][v] < INT_MAX){
                if(dis[v] > dis[u] + graph[u][v]){
                    dis[v] = dis[u] + graph[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + graph[u][v])
                    pre[v].push_back(u);
            }
        }
    }
    minCost = dis[des];

    dfs(des, happiness[des]);                   //！！！由于路径中存放的是每个节点的前驱节点 故从终点开始
    aveHap = maxHap / (path.size() - 1);
    printf("%d %d %d %d\n", ways, minCost, maxHap, aveHap);
    printf("%s", iTOs[0].c_str());              //起点
    for(int i = path.size() - 2; i >= 0; i--){  //顺序从后向前
        printf("->%s", iTOs[path[i]].c_str());
    }
    return 0;
}      

4，解题过程