不知道哪里错了

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

1C8c7h60 @ 2023-03-31 14:22:36

//单源最短路——Dijsktra算法
#include<bits/stdc++.h>
using namespace std;
//边的结构体
struct Edge{
    int v,e;
    struct Edge* next;
};
const int N=1e5+9;
char flag[N];                               //标识数组
int l[N];                                   //长度数组
//自定义的结构体排序
struct rule{
    bool operator()(const int& a,const int& b){
        return l[a]>l[b];
    }
};
int main(){
    //freopen("d:\\luogu\\P4779test1.txt","r",stdin);
    memset(l,0x3f,sizeof(l));                   //长度数组及标识数组的初始化
    memset(flag,false,sizeof(flag));            
    int n,m,s,k,count=0;
    cin>>n>>m>>s;                                   //输入
    vector<Edge*> v(n+9,NULL);                      //邻接表的存储数组
    priority_queue<int,vector<int>,rule> q;                                     //优先队列
    l[s]=0;
    q.push(s);
    for(int i=0;i<m;i++){
        int v1,v2,e;
        cin>>v1>>v2>>e;
        if(!v[v1]){                                 //用邻接表存储及其初始化
            v[v1]=new Edge;
            v[v1]->v=v2;
            v[v1]->e=e;
            v[v1]->next=NULL;
        }
        else{
            Edge* p=new Edge;
            p->v=v2;
            p->e=e;
            p->next=v[v1]->next;
            v[v1]->next=p;
        }
    }
    /*for(int i=1;i<=n;i++){
        Edge* p=v[i];
        while(p){
            cout<<i<<"->"<<p->v<<' '<<p->e<<endl;
            p=p->next;
        }
    }*/
    while(1){                                   //Dijsktra算法的核心
        int k=q.top();
        //cout<<"k = "<<k<<endl;
        if(flag[k]){
            q.pop();
            continue;
        }
        Edge* p=v[k];
        while(p){
            if(flag[p->v]==false){
                l[p->v]=min(l[k]+p->e,l[p->v]);                         //更新长度数组
                q.push(p->v);
            }
            p=p->next;
        }
        flag[k]=true;
        q.pop();
        count++;
        //cout<<"count = "<<count<<endl;
        if(count==n)
            break;
    }
    for(int i=1;i<=n;i++){
        cout<<l[i]<<' ';                            //输出
    }
    return 0;
}

by fanwenbing @ 2023-04-16 18:57:07

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int> PII;

const int N=2e5+10;

int dist[N],e[N],ne[N],w[N],h[N],idx,n,m,s;

bool st[N];

priority_queue<PII,vector<PII>,greater<PII>> heap;

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void Dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    heap.push({0,1});
    while(heap.size()){

        auto t=heap.top();
        heap.pop();

        int ver=t.second,length=t.first;
        if(st[ver]) continue;
        st[ver]=1;

        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>length+w[i])
            {
                dist[j]=length+w[i];
                heap.push({dist[j],j});
            }

        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m>>s;

    while(m--){
        int x,y,z;
        cin>>x>>y>>z;

        add(x,y,z);

    }

    Dijkstra();

    for(int i=1;i<=n;i++)
    cout<<dist[i]<<" ";

    return 0;
}