1131 Subway Map (30 分)
给定地铁线路，找出最佳路径。最佳两个标尺：
- 总经过站数最少
- 少换乘
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;
}
