题解：CF1486E Paired Payment

· · 题解

算多维最短路的模板了吧。

类似于 dp，维护三个状态：

以下设 dist 为最短路数组，w_{a,b} 指 a \to b 的边权。

转移：

dist_{j,w_{u,j},1}=\min_{u \to j}{dist_{u,0,0}} dist_{j,0,0}=\min_{u \to j} dist_{u,sc,1} + (sc+w_{u,j})^2

最后输出即可。

代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
const int N=1e5+10;
int h[N<<2],w[N<<2],e[N<<2],ne[N<<2],idx;
inline void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
long long dist[N][110][2];
bool st[N][110][2];
struct node{
    int u;
    long long sc,dis;
    bool now;
    bool operator<(const node &t)const{
        return dis>t.dis;
    }
};
void dj(){
    priority_queue<node> q;
    q.push({1,0,0,0});
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1][0][0]=0;
    while(q.size()){
        node t=q.top();
        q.pop();
        int u=t.u;
        long long sc=t.sc;
        bool now=t.now;
        if(st[u][sc][now]){
            continue;
        }
        st[u][sc][now]=1;
//      cout<<u<<' '<<sc<<' '<<now<<' '<<dist[u][sc][now]<<endl;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(now==0){
                if(dist[j][w[i]][1]>dist[u][0][0]){
                    dist[j][w[i]][1]=dist[u][0][0];
                    q.push({j,w[i],dist[j][w[i]][1],1});
                }
            }else{
                if(dist[j][0][0]>dist[u][sc][1]+(sc+w[i])*(sc+w[i])){
                    dist[j][0][0]=dist[u][sc][1]+(sc+w[i])*(sc+w[i]);
                    q.push({j,0,dist[j][0][0],0});
                }
            }
        }
    }
}
long long ans[N];
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dj();
    for(int i=1;i<=n;i++){
        if(dist[i][0][0]>=1e18){
            dist[i][0][0]=-1;
        }
        printf("%lld ",dist[i][0][0]);
    }
    return 0;
}