PAT Advanced 1131 Subway Map (30 )
程序员文章站
2024-03-17 14:22:22
...
PAT Advanced 1131 Subway Map (30 )
题目描述
Input Specification:
Output Specification:
Sample Input:
Sample Output:
解题思路
暴力Dfs,注意输出%04d
,因为这个有3个测试点没过,还以为是算法问题。。
Code
- AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int station[maxn], vis[maxn];
unordered_map<int, int> line;
vector<int> nextStation[maxn], res, resLine;
int minStop, st, ed;
void dfs(int preLine, int cur, int cntStop, vector<int> &path, vector<int> &transferLine) {
if(minStop != -1 && cntStop > minStop) return;
if(cur == ed) {
if(minStop == -1 || cntStop < minStop) {
minStop = cntStop;
res = path;
resLine = transferLine;
} else if(cntStop == minStop && resLine.size() > transferLine.size()) {
res = path;
resLine = transferLine;
}
return ;
}
for(int i = 0; i<nextStation[cur].size(); i++) {
int tempNext = nextStation[cur][i];
if(!vis[tempNext]) {
vis[tempNext] = 1;
int flag = 0, curLine = preLine;
if((!station[cur] && preLine != line[cur*10000+tempNext]) || (cur == st)) {
path.push_back(cur);
curLine = line[cur*10000+tempNext];
transferLine.push_back(curLine);
flag = 1;
}
dfs(curLine, tempNext, cntStop+1, path, transferLine);
if(flag) {
path.pop_back();
transferLine.pop_back();
}
vis[tempNext] = 0;
}
}
}
int main() {
freopen("in.txt", "r", stdin);
int N, M, K;
cin >> N;
memset(station, -1, sizeof(station));
for(int i = 1; i<=N; i++) {
cin >> M;
int pre = -1, cur = -1;
for(int j = 0; j<M; j++) {
pre = cur;
cin >> cur;
if(j != 0) {
nextStation[cur].push_back(pre);
nextStation[pre].push_back(cur);
line[pre*10000+cur] = line[cur*10000+pre] = i;
}
if(station[cur] == -1) {
station[cur] = i;
} else {
station[cur] = 0;
}
}
}
cin >> K;
for(int i = 0; i<K; i++) {
cin >> st >> ed;
memset(vis, 0, sizeof(vis));
minStop = -1;
vis[st] = 1;
vector<int> path, transferLine;
dfs(-1, st, 0, path, transferLine);
res.push_back(ed);
printf("%d\n", minStop);
for(int j = 1; j<res.size(); j++) {
int pre = res[j-1], cur = res[j];
printf("Take Line#%d from %04d to %04d.\n", resLine[j-1], pre, cur);
//cout << "Take Line#" << resLine[j-1] << " from " << pre << " to "<< cur << ".\n";
}
}
return 0;
}
总结
- 输出数字时一定要注意格式要求
推荐阅读
-
PAT Advanced 1131 Subway Map (30 )
-
PAT甲级 -- 1131 Subway Map (30 分)
-
PAT 甲 1131 Subway Map (30 分)
-
PAT 1131 Subway Map (30分)
-
PAT甲级 1131 Subway Map (30)
-
PAT 1131 Subway Map(30 分)
-
【PAT甲级】1022 Digital Library (30)(map)
-
PAT甲级 1022 Digital Library (30) map映射,set
-
LCA算法实际应用 PAT (Advanced Level) Practice 1151 LCA in a Binary Tree (30分) 四种方法完成题目+tarjan详细讲解!
-
PAT甲级1111 Online Map (30分)|C++实现