悬关求调dijkstra板子

NO_OI_NO_LIFE @ 2023-12-01 20:38:29

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,m,u,v,w,dis[1000006],dis1[1000006];
bool vis[1000006];

struct edge{
    int u,v,w;
}e[1000006];int head[1000006],cnt;

struct edge1{
    int u,v,w;
}e1[1000006];int head1[1000006],cnt1;

void add(int u,int v,int w){
    e[++cnt].u=v;
    e[cnt].w=w;
    e[cnt].v=head[u];
    head[u]=cnt;
}

void add1(int u,int v,int w){
    e1[++cnt].u=v;
    e1[cnt].w=w;
    e1[cnt].v=head[u];
    head1[u]=cnt1;
}

struct node{
    int dis,id;
    bool operator<(const node &rhs)const{
        return rhs.dis<dis;
    }
};

void dijkstra(){
    priority_queue<node> q;
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        node tp=q.top();q.pop();
        int di=tp.dis;
        int u=tp.id;
        vis[u]=true;
        for(int i=head[u];i;i=e[i].v){
            int to=e[i].u,wei=e[i].w;
            if(!vis[to]&&dis[to]>dis[u]+wei){
                dis[to]=dis[u]+wei;
                q.push({dis[to],to});
            }
        }
    }
}

void dijkstra1(){
    priority_queue<node> q;
    dis1[1]=0;
    q.push({0,1});
    while(!q.empty()){
        node tp=q.top();q.pop();
        int di=tp.dis;
        int u=tp.id;
        vis[u]=false;
        for(int i=head[u];i;i=e[i].v){
            int to=e[i].u,wei=e[i].w;
            if(vis[to]&&dis1[to]>dis1[u]+wei){
                dis1[to]=dis1[u]+wei;
                q.push({dis1[to],to});
            }
        }
    }
}

int main(){
    cin>>n>>m;
    memset(dis,0x3f3f3f3f,sizeof dis);
    memset(dis1,0x3f3f3f3f,sizeof dis1);
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add1(u,v,w);
    }
    memset(vis,false,sizeof vis);
    dijkstra();
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dis[i];
    memset(vis,true,sizeof vis);
    dijkstra1();
    for(int i=1;i<=n;i++) ans+=dis1[i];
    cout<<ans<<endl;
    return 0;
}

by NO_OI_NO_LIFE @ 2023-12-01 20:39:42

首先忽略cin cout int

by Sirus_Black @ 2023-12-01 21:10:11

STL默认是大根堆，改成小根堆

by NO_OI_NO_LIFE @ 2023-12-09 21:50:01

@Sirus_Black 下次记得@我。可是我重载运算符了啊，你是什么意思？

by Chenyufeng040525 @ 2024-04-06 21:00:32

@zyh0516_lucky

找不同

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m,u,v,w,dis[1000006],dis1[1000006];
bool vis[1000006];

struct edge{
    int u,v,w;
}e[1000006];int head[1000006],cnt;

struct edge1{
    int u,v,w;
}e1[1000006];int head1[1000006],cnt1;

void add(int u,int v,int w){
    e[++cnt].u=v;
    e[cnt].w=w;
    e[cnt].v=head[u];
    head[u]=cnt;
}

void add1(int u,int v,int w){
    e1[++cnt1].u=v;
    e1[cnt1].w=w;
    e1[cnt1].v=head1[u];
    head1[u]=cnt1;
}

struct node{
    int dis,id;
    bool operator<(const node &rhs)const{
        return rhs.dis<dis;
    }
};

void dijkstra(){
    priority_queue<node> q;
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        node tp=q.top();q.pop();
        int di=tp.dis;
        int u=tp.id;
        if(vis[u]==false) continue;
        vis[u]=false;
        for(int i=head[u];i;i=e[i].v){
            int to=e[i].u,wei=e[i].w;
            if(dis[to]>dis[u]+wei){
                dis[to]=dis[u]+wei;
                q.push({dis[to],to});
            }
        }
    }
}

void dijkstra1(){
    priority_queue<node> q;
    dis1[1]=0;
    q.push({0,1});
    while(!q.empty()){
        node tp=q.top();q.pop();
        int di=tp.dis;
        int u=tp.id;
        if(vis[u]==false) continue;
        vis[u]=false;
        for(int i=head1[u];i;i=e1[i].v){
            int to=e1[i].u,wei=e1[i].w;
            if(dis1[to]>dis1[u]+wei){
                dis1[to]=dis1[u]+wei;
                q.push({dis1[to],to});
            }
        }
    }
}

signed main(){
    cin>>n>>m;
    memset(dis,0x3f3f3f3f,sizeof dis);
    memset(dis1,0x3f3f3f3f,sizeof dis1);
    for(int i=1;i<=m;i++){
        scanf("%lld %lld %lld",&u,&v,&w);
        add(u,v,w);
        add1(v,u,w);
    }
    memset(vis,true,sizeof vis);
    dijkstra();
    int ans=0;
    for(int i=2;i<=n;i++) ans+=dis[i];
    memset(vis,true,sizeof vis);
    dijkstra1();
    for(int i=2;i<=n;i++) ans+=dis1[i];
    cout<<ans<<endl;
    return 0;
}

全是细心问题

by NO_OI_NO_LIFE @ 2024-04-07 22:07:56

@Chenyufeng040525 你不回我都忘了这题了哈哈，关注先给你