乐趣区

关于算法-数据结构:PAT甲级1131-Subway-Map

jiezi

题目粗心：

给一个无向图，求出从一点到另外一点的最短门路，这里的最短，指的是从终点到起点所经验的点的数目起码，如果有多条，输入中转站点起码的。

算法思路：

一开始想到的是用 Dijkstra 算法求解该问题，然而 Dijkstra 算法更适宜求解第一标尺为边权相干问题，所以想到了 DFS，并设置其参数 depth, 用来记录在从终点到起点的遍历过程中所经验的结点个数，而后采纳全局量 minDepth 保留最小的 depth, 为了不便判断是否是直达结点问题，应用邻接矩阵存储两个连贯的点的边对应的线路，比方 2000 与 2001 连通，该边是 Line# 4 的一部分，则 G[2000][2001]=4; 应用全局变量 $minTranNum$ 记录乘坐的起码线路数目。

DFS 遍历办法：

DFS 函数中设置参数为以后结点 st, 起点 e 和深度 depth, 应用 vector<int> result 保留最优的门路,vector<int> path暂存以后门路, 首先拜访以后节点 (保留到 path 中，并设置拜访标记为 true)，而后判断是否达到起点，如果是，首先计算以后门路的直达节点数目，这里的计算方法是应用一个 set 汇合 $diffLines$ 增加所有的 线路，其大小就是乘坐的线路数目(其大小减一就是直达节点数目)，如果minDepth>depth 阐明以后门路更短，那么就更新最优门路和最优间隔和乘坐线路数目, 如果 长度雷同然而乘坐的线路起码，那么更新最优门路和乘坐线路数目，最初回溯。如果没有达到起点，就递归遍历每一个没有拜访的领接点，如果所有的领接点都曾经拜访结束，那么就回溯。

留神点：

  • 1、每一次查问都得将全局变量 minDepth，minTranNum，visited 初始化。
  • 2、如果程序没有报错，没有输入后果，查看是否 DFS 函数有回退操作(path.pop_back(),visited[st]=false)

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<unordered_set>
#include<cstring>

using namespace std;

int G[10000][10000];//G[i][j]= 4 示意 i 和 j 相连接的边在第 4 条地铁上
vector<int> path;// 暂存以后搜寻到的门路
vector<int> result;// 最优门路
vector<int> Adj[10000];// 邻接表
bool visited[10000];

int minDepth;// 最短长度
int minTranNum;// 乘坐的起码线路数目

void DFS(int st, int e, int depth){
    // 首先拜访以后节点
    path.push_back(st);
    visited[st] = true;
    if(st == e){
        // 达到起点
        // 计算乘坐的线路数目
        unordered_set<int> diffLines;// 不同的线路数目
        for (int i = 0; i < path.size() - 1; ++i) {diffLines.insert(G[path[i]][path[i+1]]);
        }
        if(minDepth>depth){
            // 以后门路更短
            result = path;
            minDepth = depth;
            minTranNum = diffLines.size();} else if(minDepth==depth&&minTranNum>diffLines.size()){
            // 长度雷同, 然而直达次数起码
            result = path;
            minTranNum = diffLines.size();}
        // 回溯
        path.pop_back();
        visited[st] = false;
        return;
    }
    // 拜访每一个领接点
    for (int next : Adj[st]) {
        // 领接点
        if(!visited[next]){DFS(next, e, depth + 1);
        }
    }
    path.pop_back();// 回溯
    visited[st] = false;
}

void print(int start,int end){printf("%d\n",minDepth);
    int current_line = G[result[0]][result[1]];// 以后线路
    int s = start;// 乘坐以后线路的终点
    for (int i = 1; i < result.size()-1; ++i) {if(G[result[i]][result[i+1]]!=current_line){
            // i 为换乘站
            printf("Take Line#%d from %04d to %04d.\n",current_line,s,result[i]);
            s = result[i];
            current_line = G[result[i]][result[i+1]];
        }
    }
    // 始终没有换乘或者以后位最初一次直达地铁线
    printf("Take Line#%d from %04d to %04d.\n",current_line,s,end);
}

int main(){
    int N;
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        int M;
        scanf("%d",&M);
        int a,b;
        for (int j = 0; j < M; ++j) {if(j==0){scanf("%d",&a);
            } else {scanf("%d",&b);
                G[a][b] = G[b][a] = i+1;
                Adj[a].push_back(b);
                Adj[b].push_back(a);
                a = b;
            }
        }
    }
    int K;
    scanf("%d",&K);
    int start,end;
    for (int k = 0; k < K; ++k) {scanf("%d %d", &start, &end);
        // 每次查问都得初始化
        minDepth = 0x3fffffff;
        minTranNum = 0x3fffffff;
        memset(visited,0, sizeof(visited));
        path.clear();
        result.clear();
        DFS(start, end, 0);
        print(start, end);// 输入出行计划
    }
    return 0;
}
退出移动版