题解：P10535 [Opoi 2024] 数据转换

· · 题解

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

题目转化

因为题目说每一类插头有 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;
}