到处出错❌ | 1131 Subway Map (30 分)

1131 Subway Map (30 分)

给定地铁线路，找出最佳路径。最佳两个标尺：

1. 总经过站数最少
2. 少换乘

DFS遍历即可。

关键是判断换乘以及用什么方法来存A站-B站属于哪条线路。

直接line[10000][10000]怕是要💥，所以一开始写的是map<pair<int, int>, int> stop_line;并且规定线路存的时候是id小的站放在pair.first, id大的放在second。

然而看了柳神题解后发现：可以进一步降维啊。已知是0000-9999，那就可以用一个int aaaabbbb来存线路了，高四位代表站A，低四位表示站B，map<int, int> stop2_line; ）

• ⬇️这是一开始的写法（绕圈判断❌）
  25分，测试点3运行超时。
  因为想到维护visited防止绕圈，但是把防止绕圈想成了防止走一样的路，明明是一条路再次走过某站就算绕圈了呜呜呜我在想什么……）
  ⚠️目测降维什么的不是超时的主因，绕圈才是。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

#define MAXN 10000
#define INF 0x3fffffff
using namespace std;
vector<int> graph[MAXN];
map<int, int> stop2_line;
map<int, bool> visited;
vector<int> path, temp_path;
int nline, trans_time, min_stops;
int nq, st, ed;

int get_road_id(int c1, int c2) {
    return 10000 * min(c1, c2) + max(c1, c2);
}

int getTransfer() {
    int res = 0, curr_line = -1, len = temp_path.size();
    for (int i = 0; i < len - 1; i++) {
        int line = stop2_line[get_road_id(temp_path[i], temp_path[i + 1])];
        if (line != curr_line) {
            res++;
            curr_line = line;
        }
    }
    return res;
}

void DFS(int root, int stops) {
    if (root == ed) {
        temp_path.emplace_back(root);
        if (stops < min_stops || (stops == min_stops && getTransfer() < trans_time)) {
            path = temp_path;
            min_stops = stops;
            trans_time = getTransfer();
        }
        temp_path.pop_back();
        return;
    }
    temp_path.emplace_back(root);
    for (auto item:graph[root]) {
        int id = get_road_id(root, item);
        if (!visited[id]) {
            visited[id] = true;
            DFS(item, stops + 1);
            visited[id] = false;
        }
    }
    temp_path.pop_back();
}

int main() {
    scanf("%d", &nline);
    for (int i = 1; i <= nline; ++i) {
        int span, curr, next;
        scanf("%d%d", &span, &curr);
        for (int j = 1; j < span; ++j) {
            scanf("%d", &next);
            graph[curr].emplace_back(next);
            graph[next].emplace_back(curr);
            stop2_line[get_road_id(curr, next)] = i;
            curr = next;
        }
    }
    scanf("%d", &nq);
    for (int i = 0; i < nq; ++i) {
        scanf("%d%d", &st, &ed);
        trans_time = INF, min_stops = INF;
        path.clear();
        DFS(st, 1);
        int len = path.size() - 1;
        printf("%d\n", len);
        int mm = min(st, path[1]), MM = max(st, path[1]);
        if (trans_time == 1) {
            printf("Take Line#%d from %04d to %04d.\n", stop2_line[mm * 10000 + MM], st, ed);
        } else {
            int line = stop2_line[mm * 10000 + MM], temp = st;
            for (int j = 2; j <= len; ++j) {

                if (stop2_line[get_road_id(path[j - 1], path[j])] != line) {
                    printf("Take Line#%d from %04d to %04d.\n", line, temp, path[j - 1]);
                    line = stop2_line[get_road_id(path[j - 1], path[j])];
                    temp = path[j - 1];
                }
            }
            printf("Take Line#%d from %04d to %04d.\n", line, temp, ed);
        }
    }
    return 0;
}

• 改了之后= =，30分，重复经过相同的站即绕圈 = =

  
  关键代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

#define MAXN 10000
#define INF 0x3fffffff
using namespace std;
vector<int> graph[MAXN];
map<int, int> stop2_line;
bool visited[MAXN];
vector<int> path, temp_path;
int nline, trans_time, min_stops;
int nq, st, ed;

int get_road_id(int c1, int c2) {
    return 10000 * min(c1, c2) + max(c1, c2);
}

int getTransfer() {
    int res = 0, curr_line = -1, len = temp_path.size();
    for (int i = 0; i < len - 1; i++) {
        int line = stop2_line[get_road_id(temp_path[i], temp_path[i + 1])];
        if (line != curr_line) {
            res++;
            curr_line = line;
        }
    }
    return res;
}

void DFS(int root, int stops) {
    if (root == ed) {
        temp_path.emplace_back(root);
        if (stops < min_stops || (stops == min_stops && getTransfer() < trans_time)) {
            path = temp_path;
            min_stops = stops;
            trans_time = getTransfer();
        }
        temp_path.pop_back();
        return;
    }
    temp_path.emplace_back(root);
    for (auto item:graph[root]) {
        if (!visited[item]) {
            visited[item] = true;
            DFS(item, stops + 1);
            visited[item] = false;
        }
    }
    temp_path.pop_back();
}

int main() {
    scanf("%d", &nline);
    for (int i = 1; i <= nline; ++i) {
        int span, curr, next;
        scanf("%d%d", &span, &curr);
        for (int j = 1; j < span; ++j) {
            scanf("%d", &next);
            graph[curr].emplace_back(next);
            graph[next].emplace_back(curr);
            stop2_line[get_road_id(curr, next)] = i;
            curr = next;
        }
    }
    scanf("%d", &nq);
    for (int i = 0; i < nq; ++i) {
        scanf("%d%d", &st, &ed);
        trans_time = INF, min_stops = INF;
        path.clear();
        visited[st] = true;
        DFS(st, 1);
        visited[st] = false;
        int len = path.size() - 1;
        printf("%d\n", len);
        int mm = min(st, path[1]), MM = max(st, path[1]);
        if (trans_time == 1) {
            printf("Take Line#%d from %04d to %04d.\n", stop2_line[mm * 10000 + MM], st, ed);
        } else {
            int line = stop2_line[mm * 10000 + MM], temp = st;
            for (int j = 2; j <= len; ++j) {
                if (stop2_line[get_road_id(path[j - 1], path[j])] != line) {
                    printf("Take Line#%d from %04d to %04d.\n", line, temp, path[j - 1]);
                    line = stop2_line[get_road_id(path[j - 1], path[j])];
                    temp = path[j - 1];
                }
            }
            printf("Take Line#%d from %04d to %04d.\n", line, temp, ed);
        }
    }
    return 0;
}