[C++知识库][牛客]传闻档案

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
int n,m;
vector<int> G[N];
int A[N],B[N];
bool st[N];
void dijkext(){
    priority_queue<pii,vector<pii>,less<pii> > Q;
    for(int i = 1;i <= n;i++) Q.push({B[i],i});
    while(!Q.empty()){
        int u = Q.top().y,d = Q.top().x;
        Q.pop();
        if(st[u]) continue;
        st[u] = true;
        for(int i = 0;i < G[u].size();i++){
            int v = G[u][i];
            if(!st[v] && B[v] < d){
                B[v] = d;
                Q.push({B[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",&A[i]),B[i] = A[i];
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        G[v].push_back(u);
    }
    dijkext();
    ll s = 0;
    for(int i = 1;i <= n;i++){
        s += B[i];
    }
    cout << s << endl;
    return 0;
}

堆优化版dijkstra算法变形。
反向添加有向边，堆由小顶堆改为大顶堆。

题目链接
原创不易，感谢支持。