L3-014 周游世界 (30 分)

题目

题目链接

题解

DFS。

采用的数据结构，vector，索引为起点，值为{终点，起点公司编号}，当然你也可以保存终点公司编号，但是代码中的语句就需要改一下了。

dfs，传入四个信息，当前节点、遇到的节点数、换乘数、当前节点所在公司的编号。

由于存在循环，要加入标记数组进行标记。

不敢dfs啊，而且也没想好用什么数据结构，看了大佬的题解才知道如何保存路径，才知道要用dfs，不过好歹最后自己写出来（算是）。

代码

#include<bits/stdc++.h>
#define PII pair <int, int>
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 <node> road[N];
vector <PII> 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 < best_across || (across == best_across && change < best_change)) {
			best_across = across; // 更新最少经过的节点数 
			best_change = change; // 更新最 
			best_path = path; // 记录最佳路径 
		}
		return ;
	}
	
	for (int i = 0;i < road[x].size();i ++) {
		int next_road = road[x][i].next;
		int next_company = road[x][i].company;
		
		if (st[next_road]) continue; // 遇到过了就continue 

		st[next_road] = 1; // 防止循环 
		
		if (next_company == company) // 如果下一个节点所在公司与当前节点相同，则我们不记录输出路径 
			dfs (next_road, across+1, change, next_company); // 只加经过的节点数，不加换乘数 
		else {
			// 路径记录这里需要好好理解 
			path.push_back ({x, next_company}); // 将当前节点的所在公司改为与之相连的节点的公司编号，公司发生变更，记录换乘 
			dfs (next_road, across+1, change+1, next_company);
			path.pop_back (); // 回溯 
		}
		st[next_road] = 0;
	}
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> 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 << best_across << endl;
			for (int i = 0;i < best_path.size()-1;i ++)
				printf ("Go by the line of company #%d from %04d to %04d.\n", best_path[i].second, best_path[i].first, best_path[i+1].first);
		}
	}
	return 0;
}