思路

我们考虑移动到同一点 $x$ 时，红球和蓝球走过的路径，红球走的是一条 $1\rightarrow x$ 的路径，蓝球走的是一条 $i\rightarrow x$ 的路径，记 ${\rm{dis}}(i,j)$ 表示原图中 $i$ 点到 $j$ 点的最短路长度，那么问题变成了也就是在原图中找到一点 $x$ ，使得 ${\rm{dis}}(1,x)+{\rm{dis}}(i,x)$ 最小，此时如果枚举 $x$ ，便可以在 $O(nm\log m)$ 的时间内解决，但还无法通过本题，接下来我们考虑如何把枚举 $x$ 这个步骤去掉。

我们对原图中所有边取反建立反图 $G'$，记 ${\rm{dis'}}(i,j)$ 表示 $G'$ 中 $i$ 点到 $j$ 点的最短路长度，那么问题转化成了找一个点 $x$ ，使得 ${\rm{dis}}(1,x)+{\rm{dis'}}(x,i)$ 最小，我们记 $x$ 在 $G'$ 中对应的点为 $x'$，对于 $x\in[1,n]$，用一条权值为 $0$ 的有向边连接 $x$ 和 $x'$，此时在这 $2n$ 个点构成的图中， $1$ 号点到 $i'$ 点的最短路长度，就是我们想求的最小的 ${\rm{dis}}(1,x)+{\rm{dis'}}(x,i)$，新图有 $2n$ 个节点以及 $2m+n$ 条边，因此在新图中以 $1$ 为源点求解单源最短路即可在 $O(m\log m)$ 的时间内解决问题。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

using i64 = long long;
const int MAXN = 200005;
const i64 INF = 1e18;

struct Edge {
	int v, w;
};

vector<Edge> e[MAXN];
i64 dis[MAXN]; 
bool vis[MAXN];

struct Point {
	int p;
	i64 w;
};

struct cmp {
	bool operator()(Point &a, Point &b) {
		return a.w > b.w; 
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	
	while (m--) {    
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back(Edge{v, w});
		e[v + n].push_back(Edge{u + n, w});
	}
	
	for (int i = 1; i <= n; i++) {
		e[i].push_back(Edge{i + n, 0});
	}
	
	fill(dis, dis + 2 * n + 1, INF); 
	priority_queue<Point, vector<Point>, cmp> q; 
	q.push(Point{1, 0}); 
	dis[1] = 0;
	while (!q.empty()) {
		Point head = q.top();
		q.pop();
		int now = head.p;
		if (vis[now]) continue; 
		vis[now] = true;
		for (int i = 0; i < e[now].size(); i++) {
			int v = e[now][i].v;
			int w = e[now][i].w;
			if (dis[now] + w < dis[v]) {
				dis[v] = dis[now] + w;
				q.push(Point{v, dis[v]});
			}
		}
	}
	
	for (int i = 2; i <= n; i++) {
		if (dis[i + n] == INF) cout << -1 << ' ';
		else cout << dis[i + n] << ' ';
	}
	
	return 0;
}