Moving Both Hands

Created by LXC on Sun Mar 17 17:33:39 2024

https://codeforces.com/problemset/problem/1725/M

ranting: 1800

tag: dp, graphs, shortest paths

problem

题目描述

Alice 在进行一个有向图上做游戏。有向图上共有 $n$ 个节点，$m$ 条有向边。Alice的手上有
一个红色球和一个蓝色球。
游戏开始时，Alice将红色球放在 $1$ 号节点上，将蓝色球放在 $i$ 号节点上。
长度为 $w$
的有向边表示可以通过一次操作将在 $v$ 的点转移
到 $u$
花费 $w$时间。
每局游戏中，Alice 要通过尽可能少的时间将两个球共同转移到任意同一个节点上。Alice 同一时间只能操作一个球。现在 Alice 想知道对于每个点 $2\le i \le n$
，每局游戏完成的最小时间是
多少。

输入格式

输入第一行是两个整数 $n$ ，$m$。
接下来 $m$行，每行三个整数 $u$，$v$，$w$，表示图上有一条从 $u$ 指向 $v$ 长为 $w$ 的有向边。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行的整数表示蓝色球开始时在 $i$ 号点上时游戏的
最小完成时间。如果不能完成游戏，输出 -1 。

solution

求最短路径，关键在于建图。

首先注意到如果从1到x，最终都在k点停下，那么需要从1到k的最短路径加上从x到k的最短路径。从x到k的最短路径是反向图的从k到x的最短路。所以我们需要从1到x的路径后半段是在反向图上进行的。

我们可以这样建图，我们建立2n个点的图，每个点u，建立(u, u+n, 0)。对于u到v边权为w，建立两条边(u, v, w)和(v+n, u+n, w)。

然后从1开始跑dijkstra，最后答案是1分别到n+2,n+3,n+4,…,n+n的最短路径。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;
const ll INF = 1e18;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<ll,ll>>> g(2*n+1);
    for (int i=0; i<m; i++) {
        ll x, y, w;
        cin >> x >> y >> w;
        g[x].emplace_back(y, w);
        g[y+n].emplace_back(x+n, w);
    }
    for (int i=1; i<=n; i++) {
        g[i].emplace_back(i+n, 0);
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<>> pq;
    pq.emplace(0,1);
    vector<ll> dis(2*n+1, INF), vis(2*n+1);
    dis[1] = 0;
    while (pq.size()) {
        auto [x, y] = pq.top(); pq.pop();
        if  (vis[y]) continue;
        vis[y] = 1;
        for (auto [u,w]:g[y]) {
            if (dis[u] > dis[y]+w) {
                dis[u] = dis[y]+w;
                pq.emplace(dis[u], u);
            }
        }
    }
    for (int i=n+2; i<=2*n; i++) {
        if (dis[i] == INF) cout << "-1 ";
        else cout << dis[i] << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}