题目描述

难度分:$1800$

输入$n(2 \leq n \leq 10^5)$，$m(0 \leq m \leq 2 \times 10^5)$，表示一个$n$点$m$边的有向图。节点编号从$1$开始。保证图中无自环和重边。

然后输入$m$条边，每条边输入$x$、$y$、$w(1 \leq w \leq 10^9)$，表示一条从$x$到$y$的边权为$w$的有向边。

定义$f(i)$为：有甲乙两人，分别从$1$和$i$出发，到达同一个点，两人用时之和的最小值。如果两人无法到达同一个点，则$f(i)=-1$。

输出$f(2),f(3),…,f(n)$。

输入样例

5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

输出样例

1 -1 3 4

算法

分层最短路

一般图论问题的算法非常简单，直接贴模板，难度主要还是在于建模。对于一个节点$i$，我们需要找到一个节点$x$，使得$1$到$x$的距离和$i$到$x$的距离之和最小。这个过程可以看成两段：先从节点$1$到节点$x$，然后再从节点$x$到节点$i$，这样就变成了求$1$到$i$的最短路。

因此，我们对每条有向边$x \rightarrow y$构建反向边$x+n \leftarrow y+n$，每个节点$i$拆成两个点$i$和$i+n$，它们之间用权为$0$的边连接起来。

而在求最短路的时候，节点编号$i \leq n$时可以走向编号$\leq n$的节点，也可以走向编号$\gt n$的节点。但是一旦走向$\gt n$的节点，就不能回头了，必须一直走反向边，不然两段路程中从$1$到$x$这一段就不准了。然后跑一次$Dijkstra$算法，在统计答案时对每个$i$输出$min(dist[i],dist[i+n])$。

复杂度分析

时间复杂度

整个算法过程就是一次堆优化的$Dijkstra$算法，添加完反向节点和反边之后不改变点数和边数的量级，因此时间复杂度还是$O(mlog_2n)$，其中$n$为节点数，$m$为边数。

空间复杂度

图的邻接表空间复杂度是$O(n+m)$，最短路算法要使用的距离数组$dist$和判重数组$st$都是$O(n)$级别的，因此整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 200010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<array<int, 2>> graph[N<<1];
LL dist[N<<1];
bool st[N<<1];

void dijkstra(int src) {
    dist[src] = 0;
    priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
    heap.push({0, src});
    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        for(auto& tup: graph[ver]) {
            int j = tup[0], w = tup[1];
            if(ver <= n) {
                if(dist[j] > dist[ver] + w) {
                    dist[j] = dist[ver] + w;
                    heap.push({dist[j], j});
                }
            }else {
                if(j > n) {
                    if(dist[j] > dist[ver] + w) {
                        dist[j] = dist[ver] + w;
                        heap.push({dist[j], j});
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= 2*n; i++) {
        graph[i].clear();
        dist[i] = INF;
        st[i] = false;
    }
    for(int i = 1; i <= m; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        graph[x].push_back({y, w});
        graph[y + n].push_back({x + n, w});
    }
    for(int i = 1; i <= n; i++) {
        graph[i].push_back({i + n, 0});
    }
    dijkstra(1);
    for(int i = 2; i <= n; i++) {
        LL d = min(dist[i], dist[i + n]);
        if(d == INF) d = -1;
        printf("%lld ", d);
    }
    return 0;
}