自动搬运

查看原文

来自洛谷，原作者为

	shuqiang 这个家伙不懒，但是什么也没有留下

搬运于2025-08-24 22:58:58，当前版本为作者最后更新于2024-05-28 13:25:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个题目分成两个部分，题目转化和求最短路。

题目转化

因为题目说每一类插头有 $2$ 种不同接头，种类分别为 $i$ 和 $n+i$，有且只有同一类的不同接头可以互相连接，所以存边可以存这个电线可以连的电线，而不是这个电线本身的类型，这样题目就变成一个简单的求最短路问题了。

求最短路

求最短路可以使用 Dijkstra 算法，这个算法的时间复杂度上限是 $\mathcal{O}(n^2)$，用堆优化后复杂度为$\mathcal{O}(m\log n)$，明显可以过这题。在这之前建议先完成 P3371。

Dijkstra 算法的流程：

1. 先初始化 $dis_{s}=0$，其它为无穷大。
2. 找一个最小的 $dis_{i}$，此时 $dis_{i}$ 已经是最小的，所以不可能有别的路径可以更新 $dis_{i}$，这个步骤可以用堆优化。
3. 找到所有与点 $i$ 连接的点 $j$，如果通过这个点的路径更短，更新 $dis_{j}$ 为 $dis_{i}+i$ 到 $j$ 的距离。
4. 如果全部点都访问完毕，跳出循环，否则回到第 2 步。
5. 如果 $dis_{t}$ 还是无穷大，说明无解，输出 I have no idea how to solve it.，否则输出 $dis_{t}$。

AC 代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;
typedef long long ll;

struct node{
	ll dis, u;
	bool operator > (const node & o) const{
		return dis > o.dis;
	}
};
priority_queue<node, vector<node>, greater<node>> pq;

struct Edge{
	ll to, w;
};

const int N = 1e5 * 2 + 10;
const ll inf = 1e18;
vector<Edge> e[N];
ll dis[N], n, m, s, t, u, v, w;
bool vis[N];

void dijkstra(int s){
	for(int i = 0; i < N; i++) dis[i] = inf;
	dis[s] = 0;
	pq.push({0, s});
	while(!pq.empty()){
		int u = pq.top().u;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for(auto ed: e[u]){
			int v = ed.to, w = ed.w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				pq.push({dis[v], v});
			}
		}
	}
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> u >> v >> w;
		if(v > n) v -= n;
		else v += n;
		e[u].push_back({v, w});
		if(v > n) v -= n;
		else v += n;
		if(u > n) u -= n;
		else u += n;
		e[v].push_back({u, w});
	}
	cin >> s >> t;
	if(s > n) s -= n;
	else s += n;
	dijkstra(s);
	if(dis[t] == inf) cout << "I have no idea how to solve it.";
	else cout << dis[t];
	return 0;
}