题意
给出一个 $n$ 个点 $m$ 条边的有向图，点的编号为 $1$ 到 $n$，第 $i$ 条边从 $u_i$ 出发连向 $v_i$，长度为 $w_i$。
你想要在这张图上玩若干轮游戏。在一轮游戏中，你会先选定一个点 $p \neq 1$，接着在 $1$ 号点和 $p$ 分别放置一枚金币。你可以沿着有向边任意移动金币，但需要花费边长对应的时间。你的目标是要让两枚金币移动到同一个点，并且最小化总时间。
对于每个 $2 \leq i \leq n$，你都要输出如果选定 $p = i$ 时最小的时间花费。如果两枚金币不可能移到同一个点，则输出 $−1$。
题解
比较妙的建模。
可以建一层正向图，再建一个反向图。从正向图中的一个点可以直接跃迁到反向图。而反向图不能回到正向图。
代码
dijkstra 版：
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom come.
// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0
using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = 1073741823, INF = 0x3fffffffffffffff;
// :/
void MIST() {
}
constexpr tp Hat_N = 2e5 + 3;
bool vis[Hat_N];
tp dist[Hat_N];
vector<pair<tp, tp>> e[Hat_N];
void dijkstra(tp s) {
priority_queue<pair<tp, tp>, vector<pair<tp, tp>>, greater<pair<tp, tp>>> q;
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
for (q.emplace(0, s); q.size();) {
tp l = q.top().second;
q.pop();
if (!vis[l]) {
vis[l] = true;
for (auto& t : e[l]) {
tp i = t.first, j = t.second;
if (dist[i] > dist[l] + j) {
dist[i] = dist[l] + j;
if (!vis[i]) q.emplace(dist[i], i);
}
}
}
}
}
void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
tp n, m;
cin >> n >> m;
while (m--) {
tp u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v + n].emplace_back(u + n, w);
}
for (tp i = 1; i <= n; ++i) e[i].emplace_back(i + n, 0);
dijkstra(1);
for (tp i = 2; i <= n; ++i)
cout << (dist[i + n] * 2 > INF ? -1 : dist[i + n]) << " \n"[i == n];
}
#include <fstream>
signed main() {
tp t = 0, _t = 1;
cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
static ifstream _in("input.txt");
cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
static ifstream _in(EFILE ".in");
static ofstream _out(EFILE ".out");
cin.rdbuf(_in.rdbuf());
cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
// cin >> _t;
MIST();
while (t < _t) STRUGGLING(++t);
return 0;
}
//*/