一半ac求调

P4779 【模板】单源最短路径（标准版）

CN0202deXP @ 2024-11-30 23:00:21

2，3，6ac，其余wa

#include <bits/stdc++.h>
using namespace std;

struct tu{
    int now=0;
    int next=0;
    int towhat=0;
    int lenth=0;
}a[200001];

int rc[100001];
int ans[100001];
bool chk[100001];
int n,m,s;

struct cmp{
    bool operator()(int a1,int b1){
        return ans[a1]>ans[b1];
    }
};

void dij(){
    priority_queue <int,vector<int>,cmp> qp;
    int tmp1=s;
    do{
        tmp1=rc[tmp1];
        while(a[tmp1].now!=0){
            if(a[tmp1].lenth+ans[a[tmp1].now]<ans[a[tmp1].towhat]) ans[a[tmp1].towhat]=a[tmp1].lenth+ans[a[tmp1].now];
            qp.push(a[tmp1].towhat);
            tmp1=a[tmp1].next;
        }   

        tmp1=qp.top();
        while(chk[tmp1]==true&&qp.empty()==false){
            qp.pop();
            tmp1=qp.top();
        }
        if(qp.empty()==true) break;
        chk[tmp1]=true;
        //cout<<qp.top()<<'\n';
        qp.pop();
    }while(qp.empty()==false);
    return;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int i;
    memset(ans,9999999,sizeof(ans));
    memset(chk,false,sizeof(chk));
    cin>>n>>m>>s;
    //cout<<'\n';
    ans[s]=0;
    chk[s]=true;
    for(i=1;i<=m;i++){
        cin>>a[i].now>>a[i].towhat>>a[i].lenth;
        a[i].next=rc[a[i].now];
        rc[a[i].now]=i;
    }

    dij();

    for(i=1;i<=n;i++){
        cout<<ans[i]<<' ';
        }

}

by Ben_coding @ 2024-12-05 18:49:38

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
const int M=2*1e5+10;
int n,m,s,idx,first[N],dis[N],vis[N];
struct edge{int v,w,next;}e[M];
void add_edge(int u,int v,int w){
    idx++;
    e[idx].v=v;
    e[idx].w=w;
    e[idx].next=first[u];
    first[u]=idx;
}
void Dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> >q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push({0,s});
    for (int i=1;i<=n;i++){
        int u=q.top().second;q.pop();
        while (vis[u]){u=q.top().second;q.pop();};
        vis[u]=1;
        for (int j=first[u];j;j=e[j].next){
            int v=e[j].v,w=e[j].w;
            if (dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q.push({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_edge(u,v,w);
    }
    Dijkstra(s);
    for (int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

by CN0202deXP @ 2024-12-07 17:26:11

谢谢佬%%%

|