dij 68 求助

Winston12321_ @ 2022-08-21 21:30:59

#include <iostream>
#include <vector>
#include <queue> 
using namespace std;
const int N=100010;
const int INF=2147483647;
int n,m,st;
int a;
long long dis[N];
vector<int>son[N],side[N];
bool vis[N];
struct node{int id;};
bool operator <(node a,node b){return dis[a.id]>dis[b.id];}
priority_queue<node>now;
int read()
{
    int s=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s;
}
void dij()
{
    while(true)
    {
        int temp=now.top().id;
        while(vis[temp] && !now.empty()) now.pop(),temp=now.top().id;
        if(now.empty()) return;
        now.pop();
        vis[temp]=1;
        for(int i=0;i<son[temp].size();++i) dis[son[temp][i]]=min(dis[son[temp][i]],dis[temp]+side[temp][i]),now.push(node{son[temp][i]});
    }
}
int main()
{
    n=read();
    m=read();
    st=read();
    for(int i=1;i<=m;++i) a=read(),son[a].push_back(read()),side[a].push_back(read());
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[st]=0,now.push(node{st});
    dij();
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

by Wilson_Lee @ 2022-08-21 21:42:18

@Winston12321_ 这个堆建议换一种写法

by Winston12321_ @ 2022-08-21 21:47:01

@Wilson_Lee 如何写啊？

by Wilson_Lee @ 2022-08-21 21:52:55

#include <iostream>
#include <vector>
#include <queue> 
using namespace std;
typedef pair<long long,int> pa;
const int N=100010;
const long long INF=1e18;
int n,m,st;
int a;
long long dis[N];
vector<int>son[N],side[N];
bool vis[N];
priority_queue< pa,vector<pa>,greater<pa> >now;
int read()
{
    int s=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s;
}
void dij()
{
    while(true)
    {
        int temp=now.top().second;
        while(vis[temp] && !now.empty()) now.pop(),temp=now.top().second;
        if(now.empty()) return;
        now.pop();
        vis[temp]=1;
        for(int i=0;i<son[temp].size();++i) dis[son[temp][i]]=min(dis[son[temp][i]],dis[temp]+side[temp][i]),now.push({dis[son[temp][i]],son[temp][i]});
    }
}
int main()
{
    n=read();
    m=read();
    st=read();
    for(int i=1;i<=m;++i) a=read(),son[a].push_back(read()),side[a].push_back(read());
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[st]=0,now.push({0,st});
    dij();
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

堆改成我常用的写法就能过

by WorldHim @ 2022-08-21 21:53:52

为什么不这样存边

struct node{
    int to,dis;
    bool operator<(const node &t)const{
        return t.dis<dis;
    }
};
vector <node> edge[MAXN];

by WorldHim @ 2022-08-21 21:55:06

然后就变成了这样

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=1e5+20,INF=2147483647;
struct node{
    int to,dis;
    bool operator<(const node &tmp)const{
        return tmp.dis<dis;
    }
};
vector <node> p[MAXN];
priority_queue <node> q;
int dis[MAXN];
bool vis[MAXN];
int n,m,s;
void dijkstra(){
    for(int i=0;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;
    node tmp;
    tmp.to=s,tmp.dis=dis[s];
    q.push(tmp);
    while(!q.empty()){
        node t=q.top();
        q.pop();
        if(!vis[t.to]){
            vis[t.to]=1;
            for(auto it:p[t.to])
                if(dis[t.to]+it.dis<dis[it.to]){
                dis[it.to]=dis[t.to]+it.dis;
                node tmp;
                tmp.to=it.to,tmp.dis=dis[it.to];
                q.push(tmp);
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=0,u;i<m;i++){
        node tmp;
        cin>>u>>tmp.to>>tmp.dis;
        p[u].push_back(tmp);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<' ';
    return 0;
}

by Winston12321_ @ 2022-08-21 21:55:07

@Wilson_Lee orz 我要研究一下

by TempestJueMu @ 2022-08-21 21:59:23

@Winston12321_ 可能是priority_queue 里面边权和编号都要存，可以用 pair

by dengchengzhuo @ 2022-08-21 22:22:15

oi-wiki上应该有详细解释 @Winston12321_

by Winston12321_ @ 2022-08-22 14:00:04

此贴终结

同时警示后人，直接修改dis会破坏堆的结构

---------------------------end---------------------------