您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

L3-014 周游世界 (30 分)

不牌不改 发布时间:2022-04-19 16:44:03 ,浏览量:0

题目

题目链接

题解

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             
关注
打赏
1662186765
查看更多评论
0.0432s