题目描述

难度分:$2000$

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

然后输入$m$条边，每条边输入$x$，$y$，$w(1 \leq w \leq 10^{12})$，表示有一条边权为$w$的无向边连接$x$和$y$。

然后输入一个长为$n$的数组$a(1 \leq a[i] \leq 10^{12})$。

定义$d(i,j)$为$i$到$j$的最短路长度。对于每个点$i$，输出$min(2 \times d(i,j)+a[j])$，其中$1 \leq j \leq n$。

输入样例$1$

4 2
1 2 4
2 3 7
6 20 1 25

输出样例$1$

6 14 1 25 

输入样例$2$

3 3
1 2 1
2 3 1
1 3 1
30 10 20

输出样例$2$

12 10 12 

算法

$Dijkstra$求最短路

非常巧妙的一道题，刚开始先求了个最短路树，这样就可以利用倍增比较高效地求取任意点对$(i,j)$的$d(i,j)$，然后就不会优化了。

后来发现完全没有必要，只需要建立一个超级源点$0$，让$0$到$i \in [1,n]$的所有节点$i$连上权为$a[i]$的边，$i,j \in [1,n]$时正常建图，但是边权扩展为原来的两倍。

建完图后用$Dijkstra$算法跑一遍$0$到其他所有节点的最短路就可以了，这时候所有$i$的$min_{j \in [1,n]}2 \times d(i,j) + a[j]$就是$0$到$i$的最短路长度。因为此时$0$到某个节点$i$只有$a[i]$这一条直接连边，它是必定会经过这条边的。

复杂度分析

时间复杂度

整个算法流程只执行了一次$Dijkstra$算法求最短路，时间复杂度为$O(mlog_2n)$。

空间复杂度

空间消耗就是$Dijkstra$算法的空间复杂度，图邻接表的空间为$O(n+m)$，判重表$st$和距离表$dist$都是$O(n)$的，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

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

const int N = 200010;
int n, m;
LL dist[N];
vector<PIL> graph[N];
bool st[N];

void dijkstra(int src) {
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    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&pir: graph[ver]) {
            int j = pir.first;
            LL w = pir.second;
            if(dist[j] > dist[ver] + w) {
                dist[j] = dist[ver] + w;
                heap.push({dist[j], j});
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%lld ", dist[i]);
    }
}

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