标准版过了弱化版却RE
查看原帖
标准版过了弱化版却RE
951886
niumachaoren楼主2024/7/17 11:30

求调,不知道错哪里了会RE,这代码交标准版都过了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int cnt=0,head[N],n,m,s,dis[N];
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct edge{
    int to,nxt,w;
}e[M];
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dijkstra(int s){
    for(int i=1;i<=n;i++)dis[i]=2e9;
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        while(!q.empty()&&(q.top().first)>dis[q.top().second])q.pop();
        if(q.empty())return;
        int u=q.top().second;
        q.pop(); 
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}
2024/7/17 11:30
加载中...