图论、最短路、Dijkstra

在有向图上求从所有点到达 $s$ 的最短路等价于在有向图的反图上求以 $s$ 为源点的单源最短路。

时间复杂度 $O(n \log m)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=100000000000ll;
struct Edge{int i;long long w;Edge(const int &x,const long long &y):i(x),w(y){}};
bool cmp(const Edge &x,const Edge &y){return x.w>y.w;}
priority_queue<Edge,vector<Edge>,decltype(*cmp)> q(cmp);
struct Star{int w,to,nxt;}e1[100001],e2[100001];
int n,m,cnt1,cnt2,h1[1001],h2[1001];
long long ans,dis[1001];
bool on[1001];
inline void addstar(Star *e,int *h,int &cnt,int x,int y,int w){
    e[++cnt]=Star{w,y,h[x]},h[x]=cnt;
}
void dijkstra(int s,int *h,Star *e){
    fill(dis+1,dis+n+1,inf);
    memset(on,0,sizeof(on));
    dis[s]=0ll;
    for(q.push(Edge(s,0ll));!q.empty();q.pop()){
        int now=q.top().i;
        if(on[now]) continue;
        on[now]=1;
        for(int i=h[now];i;i=e[i].nxt) if(dis[e[i].to]>dis[now]+e[i].w){
            dis[e[i].to]=dis[now]+e[i].w;
            q.push(Edge(e[i].to,dis[e[i].to]));
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        static int x,y,w;
        cin>>x>>y>>w;
        addstar(e1,h1,cnt1,x,y,w);
        addstar(e2,h2,cnt2,y,x,w);
    }
    dijkstra(1,h1,e1);
    for(int i=2;i<=n;i++) ans+=dis[i];
    dijkstra(1,h2,e2);
    for(int i=2;i<=n;i++) ans+=dis[i];
    cout<<ans<<'\n';
    return 0;
}