CF1486E Paired Payment

题目描述

给你 n(n≤1e5) 个点 m(m≤2e5) 条双向边，每条边的权值为[1,50]

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

Solution

注意 Dijkstra 的性质，先到达的并且在优先队列最前的一定是当前能向外跑的最短的。

我们设当前应更新 x \to y \to z

如果当前 x \to y 是 所有点 \to y 的较短的，就可以用它去更新x\to y \to z

而接下来如果遇到一个点 w ，有 w \to y 和 x\to y 相等，那么此时 w \to y 已经不能更新 y\to z 了

因为Dijkstra 的性质，注定有 dis[x]<dis[w]

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e5+10;
int dis[N],v[N],dp[N][51],m,n;
int mn[N];
vector<pair<int,int>> vec[N];
void init(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        vec[x].push_back(make_pair(y,w));
        vec[y].push_back(make_pair(x,w)); 
    }
}
void solve(){
    priority_queue<pair<int,int> >  q;
    memset(dis,0x3f,sizeof(dis));
    memset(mn,0x3f,sizeof(mn));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
        pair<int,int> now = q.top(); q.pop();
        int x = now.second;
        if(v[x]) continue;
        v[x]=1;
        //printf("%d\n",x);
        for(auto p:vec[x]){
            int y = p.fi;
            if(p.se>=mn[y]) continue;
            mn[y]=p.se;
            for(auto r:vec[y]){
                int t_ = r.fi;
                if(v[t_]) continue;
                if(dis[t_]>dis[x]+(p.se+r.se)*(p.se+r.se)){
                    dis[t_]=dis[x]+(p.se+r.se)*(p.se+r.se);
                    q.push(make_pair(-dis[t_],t_));
                }
            }
        } 
    }
    for(int i=1;i<=n;++i)
        if(dis[i]>=0x3f3f3f3f) printf("-1 ");
        else printf("%d ",dis[i]);
}
int main(){
    init();
    solve();
    return 0;
}