L3-014 周游世界 (30 分)

题目

题目链接

题解

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