诡异的16分求调

紫玄月 @ 2024-11-27 16:28:55

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,u[200001],w[200001],v[200001],dis[200001];
int vis[200001];
vector<pair<int,int> >G[400001];
void bfs(int s){
    memset(dis,0x3f3f3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    queue<pair<int,int> > q1;
    dis[s]=0;
    q1.push({s,0});
    while(!q1.empty()){
        int u=q1.front().first,dist=q1.front().second;
        q1.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].first;
            int w=G[u][i].second;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v])
                q1.push({v,dis[v]});
            }
        }
    }
}
signed main(){
    int s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        G[u[i]].push_back({v[i],w[i]});
    }
    bfs(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
}

by Yxy7952 @ 2024-11-27 16:32:17

@紫玄月

有 ‌Dijkstra算法，Bellman-Ford算法‌，‌Floyd算法‌，SPFA算法

by liusir146 @ 2024-11-27 16:38:26

@紫玄月dij，但没有堆优化

by Yxy7952 @ 2024-11-27 16:39:12

@liusir146

确实

by 紫玄月 @ 2024-11-27 16:43:01

二位大神能否告诉我这份代码错那了?感激不尽,给关注谢谢@Yxy7952@liusir146

by liusir146 @ 2024-11-27 16:48:16

@紫玄月

#include<bits/stdc++.h>
#define int long long
#define pi pair<int,int>
using namespace std;
int n,m,u[200001],w[200001],v[200001],dis[200001];
int vis[200001];
vector<pair<int,int> >G[400001];
priority_queue<pi,vector<pi>,greater<pi> > q1;
void bfs(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0;
    q1.push({0,s});
    while(!q1.empty()){
        int u=q1.top().second;
        q1.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].first;
            int w=G[u][i].second;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v])q1.push({dis[v],v});
            }
        }
    }
}
signed main(){
    int s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        G[u[i]].push_back({v[i],w[i]});
    }
    bfs(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
}

by liusir146 @ 2024-11-27 16:48:45

@紫玄月 对比一下，看看pi的排序以及优先队列的用法

by 紫玄月 @ 2024-11-27 16:51:38

@liusir146

意思是这个优先队列优先按照pair第一位排序是吧

by 紫玄月 @ 2024-11-27 16:52:54

这个新代码的复杂度是O(nlogn)吧

by Yxy7952 @ 2024-11-27 17:02:59

@紫玄月

32ts

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[200001];
int vis[200001];
vector<pair<int,int> >G[400001];
void bfs(int s){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int> > q1;//优先队列 
    dis[s]=0;
    q1.push(make_pair(s,0));
    while(!q1.empty()){
        int u=q1.top().first;
        //如果要用，取出来注意加负号 
        q1.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].first;
            int w=G[u][i].second;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q1.push(make_pair(v,-dis[v]));//小根堆 
            }
        }
    }
}
int main(){
    int s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back(make_pair(v,w));
    }
    bfs(s);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
}

by 紫玄月 @ 2024-11-27 17:06:44

OK,都关注了,感谢@Yxy7952@liusir146