求邻接表存图题解

liruizhou_lihui @ 2024-11-06 23:46:14

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x;
    int w;
};
int n,m,s;
vector<node> e[100005];
int a[100005];
priority_queue<int,vector<int>,greater<int>> q;
//priority_queue<int> q;
void dijkstra(int s)
{
    q.push(s);
    a[s]=0;
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        for(int i=0;i<e[u].size();i++)
        {
            node v=e[u][i];
            if(a[v.x]>a[u]+v.w)
            {
                a[v.x]=a[u]+v.w;
                q.push(v.x);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(a,0x3f3f3f3f3f3f,sizeof(a));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0x3f3f3f3f)
        {
            cout<<(1<<31)-1<<' ';
        }
        else
        {
            cout<<a[i]<<' ';
        }
    }
    return 0;
}

by lzm0107 @ 2024-11-06 23:53:28

@liruizhou_lihui 你的 q 在按什么排？

by liruizhou_lihui @ 2024-11-06 23:54:50

@lzm0107 哦放错了是大根堆

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x;
    int w;
};
int n,m,s;
vector<node> e[100005];
int a[100005];
//priority_queue<int,vector<int>,greater<int>> q;
priority_queue<int> q;
void dijkstra(int s)
{
    q.push(s);
    a[s]=0;
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        for(int i=0;i<e[u].size();i++)
        {
            node v=e[u][i];
            if(a[v.x]>a[u]+v.w)
            {
                a[v.x]=a[u]+v.w;
                q.push(v.x);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(a,0x3f3f3f3f3f3f,sizeof(a));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0x3f3f3f3f)
        {
            cout<<(1<<31)-1<<' ';
        }
        else
        {
            cout<<a[i]<<' ';
        }
    }
    return 0;
}

by lzm0107 @ 2024-11-06 23:59:12

@liruizhou_lihui 堆的比较应当按照当前预估的 dis 而不是节点的编号。

by liruizhou_lihui @ 2024-11-07 00:01:31

@lzm0107 啥意思

by lql1 @ 2024-11-09 14:47:01

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/hash_policy.hpp>     
#include <ext/pb_ds/priority_queue.hpp>  

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#define ll long long
#define elif else if
#define pf printf
#define sf scanf
#define push_back emplace_back
#define P pair<int,int>

vector<vector<P>> e;
gp_hash_table<int,int> dis,vis;
__gnu_pbds::priority_queue<P,greater<P>,pairing_heap_tag> q;
int n,m,x,y;
void dijkstra(int st){
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[st]=0;
    q.push({0,st});
    while(!q.empty()){
        P x=q.top();
        q.pop();
        if(vis[x.second]) continue;
        vis[x.second]=1;
        for(P y:e[x.second]){
            int v=y.first,w=y.second;//v编号 w权值
            if(dis[v]>dis[x.second]+w){
                dis[v]=dis[x.second]+w;
                q.push({dis[v],v});
            } 
        }       
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//  cin>>n>>m;
//  e.resize(n+1);
    cin>>n>>m>>x;
    e.resize(n+1);
    for(int i=1;i<=m;i++){
        int st,ed,w;
        cin>>st>>ed>>w;
        e[st].push_back(P{ed,w});
//      e[ed].push_back(P{st,w});
    }
//  cin>>x>>y;
    dijkstra(x);
//  cout<<dis[y];
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

@liruizhou_lihui

by Caiyu2024 @ 2024-11-11 23:16:51

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7,inf=2147483647;
struct edge{
    int to,cost;
};
struct node{
    int e,val;
    friend bool operator < (node x,node y)
    {
        return x.val>y.val;
    }
};
vector<edge>g[N];
priority_queue<node>q;
bool b[N]={0};
int dis[N],n,m;
void Dijkstra(int s)
{
    for(int i=0;i<=n;i++)   dis[i]=inf;
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty())
    {
        int u=q.top().e;
        q.pop();
        if(b[u])    continue;
        b[u]=true;
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].to,l=g[u][i].cost;
            dis[v]=min(dis[v],dis[u]+l);
            q.push((node){v,dis[v]});
        }
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int s,u,v,l;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>l;
        g[u].push_back((edge){v,l});
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<' ';
    }
    return 0;
}

by Light_LE @ 2024-11-15 22:45:31

建议用链式向前星，我试过，耗时比邻接表少

// 邻接表存图
#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct GraphData {
    int v, w;
};
struct Data {
    int dis, u;
    bool operator < (const Data &x) const {
        return x.dis < dis;
    }
};
int n, m, s, vis[maxn], dis[maxn];
vector<GraphData> G[200003];
priority_queue<Data> q;
void dijkstra() {
    fill(dis + 1, dis + n + 1, INT_MAX);
    dis[s] = 0;
    q.push((Data){0, s});

    while (q.size()) {
        Data f = q.top();
        q.pop();
        int u = f.u;

        if (vis[u]) {
            continue;
        }
        vis[u] = 1;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (vis[v] == 0) {
                    q.push((Data){dis[v], v});
                }
            }
        }
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back((GraphData){v, w});
    }

    dijkstra();

    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}