共计 2487 个字符,预计需要花费 7 分钟才能阅读完成。
题目粗心:
给一个无向图,求出从一点到另外一点的最短门路,这里的最短,指的是从终点到起点所经验的点的数目起码,如果有多条,输入中转站点起码的。
算法思路:
一开始想到的是用 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;
}
正文完