自动搬运

查看原文

来自洛谷，原作者为

	Warriors_Cat 欢迎来到这方净土，这里曾有一位普通人建造着自己的乌托邦。

搬运于2025-08-24 22:14:12，当前版本为作者最后更新于2019-12-07 11:22:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

又来码题解咯~~

其实只是为了补一下咕值QAQ

首先，看到这一道题，我第一步想到的就是最短路。

为什么？蒟蒻的灵魂拷问QAQ

因为这道题在一定程度上是可以把公交车信息转化成一个图，而最少转车次数就是它的最短路。

所以，我们可以预处理出这样的一个图，然后就用堆优化$dijkstra$模板跑一遍最短路就可以了。

那么，我们怎么建图呢？

首先，在一条信息之内，每两个公交车站可以互相到达，不需要换车，于是这两个公车站之间的权值为$0$；

其次，对于同一个车站，我们可以枚举出两条信息都有没有包含这一个车站。如果有，就在它们之间连一条权值为$1$的边。

于是，建图就这样大功告成了！0^_^0

$Code$如下：

void Add_nei(){
	for(int k = 1; k <= m; ++k){
		for(int i = 1; i < mp[k][0]; ++i){
			for(int j = i + 1; j <= mp[k][0]; ++j){
				int x, y, z, w;
				x = z = k;
				y = mp[k][i], w = mp[k][j];
				add(x * 1000 + y, z * 1000 + w, 0);//相同信息内两个车站的连边
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(vis[j][i]){
				int x, y, z, w;
				x = j, y = i, w = i;
				for(int k = 1; k <= m; ++k){
					if(k == j) continue;
					if(vis[k][i]){
						z = k;
						add(x * 1000 + y, z * 1000 + w, 1);//相同车站的连边
					}
				}
			}
		}
	}
	return;
}

当然，这道题还有许多需要处理的地方：

$i.$输入。这里是以换行符为分界点来输入的。大家可以用手写快读来处理输入，我用的是$string$的$getline$输入。

$ii.$节点表示。因为这里涉及到公交车信息，所以我们需要同时存储信息编号和公交车站编号。但，为了前向星链表的存储，我是用的是哈希，节约空间。

$iii.$最后输出。注意输出时应当每个信息里的$n$号车站的最小值。

于是，这道题就这么结束了……

接下来上完整$Code$啦~~

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cctype>
#include <string>
using namespace std;
int m, n, mp[110][510], ans = 0x7fffffff;
bool vis[110][510];
string s;
struct edge{
	int v, w, nxt;
}e[2500010];
int head[2500010], cnt, dis[2500010];
inline void add(int u, int v, int w){//前向星 
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
void work(int k){//输入处理 
	int sz = s.size();
	for(int i = 0; i < sz; ++i){
		int x = 0;
		while(s[i] >= '0' && s[i] <= '9'){
			x = (x << 3) + (x << 1) + (s[i] ^ 48);
			++i;
		}
		mp[k][++mp[k][0]] = x;
		vis[k][x] = 1;
	}
	return; 
}
void Add_nei(){//建图 
	for(int k = 1; k <= m; ++k){
		for(int i = 1; i < mp[k][0]; ++i){
			for(int j = i + 1; j <= mp[k][0]; ++j){
				int x, y, z, w;
				x = z = k;
				y = mp[k][i], w = mp[k][j];
				add(x * 1000 + y, z * 1000 + w, 0);//相同信息内两个车站的连边
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(vis[j][i]){
				int x, y, z, w;
				x = j, y = i, w = i;
				for(int k = 1; k <= m; ++k){
					if(k == j) continue;
					if(vis[k][i]){
						z = k;
						add(x * 1000 + y, z * 1000 + w, 1);//相同车站的连边
					}
				}
			}
		}
	}
	return;
}
struct node{
	int u, d;
	bool operator<(const node&rhs)const{
		return d > rhs.d;
	}
};
priority_queue <node> q;
void Dij(){//dijkstra模板 
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			dis[j * 1000 + i] = 0x3f3f3f3f;
		}
	}//最小值初始化最大 
	for(int i = 1; i <= m; ++i) dis[i * 1000 + 1] = 0;//车站1为0 
	for(int i = 1; i <= m; ++i) if(vis[i][1]) q.push((node){i * 1000 + 1, 0});
	while(!q.empty()){
		node data = q.top();
		q.pop();
		int u = data.u, d = data.d;
		if(d != dis[u]) continue;
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].v, w = e[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push((node){v, dis[v]});
			}
		}
	}
	return;
}
int main(){
	scanf("%d%d", &m, &n);
	getline(cin, s);
	for(int i = 1; i <= m; ++i){
		getline(cin, s);
		work(i);
	}
	Add_nei();
	Dij();
	for(int i = 1; i <= m; ++i) ans = min(ans, dis[i * 1000 + n]);//取最小值 
	if(ans == 0x3f3f3f3f){//注意特判 
		printf("NO"); 
		return 0;
	}
	printf("%d", ans);
	return 0;
}

这篇题解就到此结束了，求大家的资瓷QAQ

帮忙点个赞呗

End