题解

固定会合点 $v$ 后，两个人各走各的，彼此没有影响，所以双方都可以选择到 $v$ 的最短路。

记原图中从 $x$ 到 $y$ 的最短距离为 $d(x,y)$，允许会合的地点集合为 $S$。第二个人从 $p$ 出发，所求就是

$$ans_p=\min_{v\in S}\bigl(d(1,v)+c_v+d(p,v)\bigr).$$

第一人的起点始终是 $1$，先从 $1$ 跑一遍 Dijkstra，所有 $d(1,v)$ 就都知道了。如果某个会合点连第一人都到不了，可以直接排除。

现在给每个剩下的会合点记一个费用

$$b_v=d(1,v)+c_v.$$

这部分与 $p$ 无关。剩下的问题变成了，第二个人从 $p$ 出发，走到某个会合点，再付这个点的 $b_v$，最少一共花多少。

从会合点往回算

先只考虑一个会合点 $v$。我们要知道所有 $p$ 到 $v$ 的距离。把边反过来，从 $v$ 跑一次最短路，就能同时得到它们，因为原图中 $p\to v$ 的路径，在反图中恰好变成同长度的 $v\to p$。

不过，会合点有很多个，不能每个点都跑一遍。它们都在同一张反图上传播距离，区别只是起始费用不同，可以把这些传播放进同一个堆里。

初始化每个允许会合且第一人可达的点为 $b_v$，其他点为无穷大，把所有有限的初值放入堆，接着在反图上正常跑 Dijkstra。

这里不能把源点距离全部设为 $0$。每个源点的初值里，已经包括第一人去这里的路费和一次服务费。

为什么一次最短路就能取到这个最小值

可以临时添加一个源点 $s$，从 $s$ 向每个会合点 $v$ 连一条权为 $b_v$ 的边，其余边采用反图的边。

从 $s$ 走到 $p$，第一条边会选定一个会合点 $v$，之后在反图中从 $v$ 走到 $p$。最短费用就是

$$\min_{v\in S}\bigl(b_v+d(p,v)\bigr),$$

与要计算的答案相同。所有边权都非负，Dijkstra 可以使用。实际程序不必真的建 $s$，把各个 $b_v$ 作为初始距离入堆即可。

整个过程只跑两遍最短路，第一遍在原图上从 $1$ 出发，第二遍在反图上用多个不同的初值出发。第二遍仍不可达的点输出 $-1$。

使用懒删除的二叉堆，时间复杂度为 $O((n+m)\log(n+m))$，空间复杂度为 $O(n+m)$。距离和费用之和用 long long，无穷大取足够大的数，且不要把无穷大的初值放入堆。

即使 $p=1$，题目里也仍是两个人，各自的行走费用都要算，不能直接把答案写成 $0$。

几种简化情况

当 $n,m\le300$，Floyd 求出全部距离，再代入开头的式子枚举会合点即可。时间 $O(n^3+nk+m)$、空间 $O(n^2)$，对应 10 分。重边取最小权，自己到自己的距离为 $0$。

当图等价于无向图、每个点都能免费会合，答案就是 $d(1,p)$。双方到任意会合点的路线拼起来，都是一条从 $1$ 到 $p$ 的路，所以总长不小于 $d(1,p)$；直接在 $p$ 会合又能达到这个下界。一遍 Dijkstra 对应这一档的 10 分。

只有一个会合点 $t$ 时，从反图的 $t$ 跑一遍 Dijkstra。设得到的距离为 $r_p$，答案是 $r_1+r_p+c_t$，遇到不可达就输出 $-1$。这一档 15 分，也直接提示了反图的用法。上面两种最短路方法的时空复杂度与完整做法同阶。

DAG 的 15 分可以不用堆。先按拓扑序求第一人的最短路 $D_u$，再设可会合点的初值为 $D_u+c_u$，按逆拓扑序计算

$$ans_u=\min\left(\text{在 }u\text{ 会合的费用},\ \min_{u\to v}(w_{u,v}+ans_v)\right).$$

第二个人要么就在 $u$ 会合，要么先走一条出边，这个转移已经包含所有选择；后继先算，当前点就可以直接取最小值。总时间和空间都是 $O(n+m)$。这四种做法按输入条件组合，可保证前四档的 50 分。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
using namespace std;
using ll = long long;
const ll INF = (1LL << 62);
using Graph = vector<vector<pair<int, int>>>;

vector<ll> dijkstra(const Graph &g, vector<ll> d) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 1; i < (int)d.size(); ++i)
        if (d[i] < INF) pq.push({d[i], i});
    while (!pq.empty()) {
        ll du = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (du != d[u]) continue;
        for (auto e : g[u]) {
            int v = e.first, w = e.second;
            if (d[v] > du + w) {
                d[v] = du + w;
                pq.push({d[v], v});
            }
        }
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    Graph g(n + 1), rg(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        rg[v].push_back({u, w});
    }
    vector<pair<int, int>> meet(k);
    for (auto &e : meet) cin >> e.first >> e.second;
    vector<ll> d(n + 1, INF);
    d[1] = 0;
    d = dijkstra(g, d);
    vector<ll> ans(n + 1, INF);
    for (auto e : meet)
        if (d[e.first] < INF) ans[e.first] = d[e.first] + e.second;
    ans = dijkstra(rg, ans);
    for (int i = 1; i <= n; ++i)
        cout << (ans[i] == INF ? -1 : ans[i]) << (i == n ? '\n' : ' ');
    return 0;
}