PAT 甲级 刷题日记|A 1131 Subway Map (

conjunction 结合 连接 同时发生

思路

这是一道典型的搜索类型的题目，处理起来比较麻烦。

寻找路径最短且换乘次数最少的路径，关键在于换乘次数最少的处理，由于站点所属路线不唯一，而每段道路所属路线是唯一的，所以可以存储路线来方便地判断换乘次数。

代码

# include<bits/stdc++.h>
using namespace std;

int const maxn = 10000 + 2;
vector<int> gra[maxn];
int edge[maxn][maxn];
int visit[maxn];
int q1, q2;
int minstep, mintrans;
vector<int> path, tempath;

int tranferCnt(vector<int> a) {
    int trans = 0;
    int preline = -1;
    for (int i = 1; i < a.size(); i++) {
        if (edge[a[i]][a[i - 1]] != preline) {
            trans++;
            preline = edge[a[i]][a[i - 1]];
        }
    }
    return trans;
}

void dfs(int id, int step) {
    if (id == q2 && (step < minstep || (step == minstep && tranferCnt(tempath) < mintrans))) {
        minstep = step;
        mintrans = tranferCnt(tempath);
        path = tempath;
    }
    if (id == q2) {
        return;
    }
    for (int i = 0; i < gra[id].size(); i++) {
        if (visit[gra[id][i]] == 0) {
            visit[gra[id][i]] = 1;
            tempath.push_back(gra[id][i]);
            dfs(gra[id][i], step + 1);
            visit[gra[id][i]] = 0;
            tempath.pop_back();
        }
        
    }
    
}

int main() {
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int ro;
        cin>>ro;
        int num[102];
        for (int j = 0; j < ro; j++) {
            cin>>num[j];
            if (j > 0) {
                gra[num[j]].push_back(num[j - 1]);
                gra[num[j - 1]].push_back(num[j]);
                edge[num[j - 1]][num[j]] = edge[num[j]][num[j - 1]] = i;
            }
        }
    }
    int q;
    cin>>q;
    while (q--) {
        cin>>q1>>q2;
        minstep = 9999;
        mintrans = 9999;
        fill(visit, visit + maxn, 0);
        tempath.clear();
        tempath.push_back(q1);
        visit[q1] = 1;
        dfs(q1, 0);
        printf("%d\n", minstep);
        int preline = edge[path[1]][path[0]];
        int star = q1;
        for (int a = 1; a < path.size(); a++) {
            if (edge[path[a]][path[a - 1]] != preline) {
                if (preline != 0) printf("Take Line#%d from %04d to %04d.\n", preline, star, path[a - 1]);
                preline = edge[path[a]][path[a - 1]];
                star = path[a - 1];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", preline, star, q2);
    }
}