题目
题目链接
题解DFS。
采用的数据结构,vector,索引为起点,值为{终点,起点公司编号},当然你也可以保存终点公司编号,但是代码中的语句就需要改一下了。
dfs,传入四个信息,当前节点、遇到的节点数、换乘数、当前节点所在公司的编号。
由于存在循环,要加入标记数组进行标记。
不敢dfs啊,而且也没想好用什么数据结构,看了大佬的题解才知道如何保存路径,才知道要用dfs,不过好歹最后自己写出来(算是)。
代码#include
#define PII pair
using namespace std;
const int N = 1e5+10, INF = 0x3f3f3f3f;
struct node {
int next, company;
};
int n, k, a, b, s, t;
int st[N], best_across = INF, best_change = INF;
vector road[N];
vector path, best_path;
void dfs (int x, int across, int change, int company) { // x表示当前节点(编号) across表示经过的节点数量(含x) change表示换乘次数(含x) companny表示x所在公司编号(x可能存在于多个公司)
// 剪枝
if (across > best_across || (across == best_across && change > best_change))
return ;
if (x == t) {
if (across k;
cin >> a; // 先获取第一个节点
while (-- k) {
cin >> b;
road[a].push_back ({b, i}); // 加双向边
road[b].push_back ({a, i});
a = b;
}
}
cin >> k;
while (k --) {
cin >> s >> t;
// 注意每次都需要初始化
memset (st, 0, sizeof st);
best_path.clear ();
path.clear ();
best_across = INF;
best_change = INF;
st[s] = 1; // 标记起点
dfs (s, 0, 0, 0); // 初始公司编号可以设置为不存在的一个值
if (!best_path.size()) puts ("Sorry, no line is available.");
else {
best_path.push_back ({t, 0}); // 保证输出终点,这样就不用单独输出从某个点到终点的信息了
cout
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?