堆优化dijkstra

与模板没有区别

在建图时$+n$反向建边，可以减小码量

#include<bits/stdc++.h>
using namespace std;
constexpr const int N=3e5+7;
int n,m;
struct edge{
    int to,nxt,w;
}t[N];
struct node{
    int dis,u;
    bool operator <(const node&x)const{
        return x.dis<dis;
    }
};
priority_queue<node>q;
bool vis[N];
int tot,dis[N],head[N];
void addedge(int u,int v,int w){
    t[++tot].nxt=head[u];
    t[head[u]=tot].to=v;
    t[tot].w=w;
    return ;
}
void dijkstra(int s){
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(int i=head[u];i;i=t[i].nxt){
            int v=t[i].to,w=t[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v+n,u+n,w);
    }
    memset(dis,0x3f,sizeof(dis));
    long long ans=0;
    dijkstra(1);
    for(int i = 2; i <= n ; i++)
        ans += dis[i];
    dijkstra(1 + n);
    for(int i = 2 + n; i <= n + n; i++) 
		ans += dis[i];
    cout<<ans<<'\n';
    return 0;
}