诡异的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 17:18:02

@紫玄月

我去，A了

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[100005];
int vis[100005];
vector<pair<int,int> >G[100005];
void bfs(int s){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int> > q1;//优先队列 
    dis[s]=0;
    q1.push(make_pair(0,s));
    while(!q1.empty()){
        pair<int,int> ud=q1.top();
        q1.pop();
        int u=ud.second;
        //如果要用，取出来注意加负号 
        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(-dis[v],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 Yxy7952 @ 2024-11-27 17:19:35

@liusir146

@紫玄月@紫玄月@liusir146@liusir146

不是，结果要改这里，这是啥错误

 int u=q1.front().first,dist=q1.front().second;

by Yxy7952 @ 2024-11-28 14:10:19

@紫玄月@liusir146

哦，我知道为什么这样改是对的了，因为优先队列是以第一关键字排序！！！！

by 紫玄月 @ 2024-11-28 14:14:31

@Yxy7952

包的

by Jackylin @ 2024-12-13 11:14:27

堆默认是大根堆，而Dijk算法需要用到小根堆，可以这样写：

typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;