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

chenzhaoxu2027 · 2024-05-27 20:31:15 · 题解

前言

官方题解我完全不懂，我不太会这种最短路 DIJ 上边的 DP，所以我写的是一种奇妙做法，竟然 AC 了？

分析

首先，我们假定编号小于 n 的插头是凹的，其他插头是凸的。

数据线的连接遵循以下规律（= 是直接插入，- 是数据线连接。）：电脑 1=a_1-b_1=a_2-b_2=\dots=a_{m-1}-b_{m-1}=a_m-b_m= 电脑 2。

所以不妨把一个等于与一个杠看为整体，比如说命名为 \odot，那么连接过程变为：电脑 1\odot b_1\odot b_2\odot \dots \odot b_{m-1}\odot b_m= 电脑 2。

所以说，只要把 \odot 关系看作边，电脑 2 给换成互补的插头，再跑一遍最短路即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge{
    int to,dis,next;
}e[500005];//前向星
int head[200005],dis[200005],cnt;
bool vis[200005];
int n, m, s;
int canmatch(int x){//求互补点
    if(x>n){
        return x-n;
    } 
    return x+n;
}
void add_edge( int u, int v, int d ){
    cnt++;
    e[cnt].dis=d;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct node{
    int dis,pos;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
};
priority_queue<node> q;
void dij(){
    dis[s]=0;
    q.push({0,s});
    while(q.size()){//堆优化 dij
        node tmp=q.top();
        q.pop();
        int x=tmp.pos,d=tmp.dis;
        if(vis[x]){
            continue;
    }
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].dis){
                dis[y]=dis[x]+e[i].dis;
                if(vis[y]==0){
                    q.push({dis[y], y});
                }
            }
        }
    }
}
int t;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=2*n;i++){
        dis[i]=2e18;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(canmatch(u),v,w);
        add_edge(canmatch(v),u,w);
    } 
    cin>>s>>t;
    t=canmatch(t);
    dij();
    if(dis[t]==2e18){
        cout<<"I have no idea how to solve it.";
    }
    else{
        cout<<dis[t];
    }
    return 0;
}