E. Paired Payment 题解(多维最短路)

题目链接

题目大意

给你\(n(n\leq 1e5)\)个点$ m(m\leq 2e5)$条双向边，每条边的权值为1-50

但是一次至少走两步，权值为两个边边权和的平方。求1到其他每个点的最短距离

题目思路

首先如果重构图那么最坏情况下边的长度会变成\(n^2\)级别的，显然不行

要发现这个边权很小，适合记录，显然奇偶也是要记录下来的

设\(dp[pos][last][odd]\)为当前在pos位置,上一条边长度为last,且走过的边数量为奇数(odd=1)/偶数(odd==0)

然后跑一遍dij即可

注意结构体重载的符号

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+5,inf=0x3f3f3f3f;
const double eps=1e-3;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int head[maxn],cnt;
ll dis[maxn][51][2];
struct edge{
    int to,nxt,w;
}e[maxn<<2];
struct node{
    ll len;
    int pos,last,odd;
    friend bool operator<(struct node a,struct node b){
        return    a.len>b.len;
    }        //这里的形式是固定的
    // 注意这是重载小于号
};
void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
void dij(int x){
	priority_queue<node > que;
	memset(dis,0x3f,sizeof(dis));
	dis[x][0][0]=0;
	que.push({0,x,0,0});
	while(!que.empty()){
		ll len=que.top().len;
		int pos=que.top().pos;
		int last=que.top().last;
		int odd=que.top().odd;
		que.pop();
		if(len!=dis[pos][last][odd]) continue;
        for(int i=head[pos];i;i=e[i].nxt){
            int to=e[i].to;
            int w=e[i].w;
            if(odd==0){
                if(dis[to][w][odd^1]>dis[pos][last][odd]){
                    dis[to][w][odd^1]=dis[pos][last][odd];
                    que.push({dis[to][w][odd^1],to,w,odd^1});
                }
            }else{
                if(dis[to][w][odd^1]>dis[pos][last][odd]+(last+w)*(last+w)){
                    dis[to][w][odd^1]=dis[pos][last][odd]+(last+w)*(last+w);
                    que.push({dis[to][w][odd^1],to,w,odd^1});
                }
            }
        }
	}
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    dij(1);
    for(int i=1;i<=n;i++){
        ll mi=INF;
        for(int j=0;j<=50;j++){
            mi=min(mi,dis[i][j][0]);
        }
        if(mi==INF) mi=-1;
        printf("%lld ",mi);
    }
    return 0;
}