为什么原AC的dijsktra全TLE???

P4779 【模板】单源最短路径(标准版)

_Kamisato_Ayaka_ @ 2024-02-01 11:37:56

原AC代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 2e5+20;
int n,m,x,k=0;
int head[N],dij[N];
struct node{
    int v,w,nxt;
}edge[N];
void add(int u,int v,int w){
    edge[++k].v=v;
    edge[k].w=w;
    edge[k].nxt=head[u];
    head[u]=k;
}
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > R;
int dijkstra(int x){
    memset(dij,0x3f,sizeof(dij));
    dij[x]=0;
    R.push(make_pair(0,x));
    while(!R.empty()){
        int u=R.top().second,t=R.top().first;
        R.pop();
        if(t!=dij[u])
            continue;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v,w=edge[i].w;
            if(dij[u]+w<dij[v]){
                dij[v]=dij[u]+w;
                R.push(make_pair(dij[v],v));
            }
        }
    }
}
int read(){
    int f=1;
    long long res=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
signed main(){
    n=read(),m=read(),x=read();
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    dijkstra(x);
    for(int i=1;i<=n;i++)
        printf("%d%c",dij[i]," \n"[i==n]);
    return 0;
}

by _Kamisato_Ayaka_ @ 2024-02-01 11:38:23

提交记录 https://www.luogu.com.cn/record/list?pid=P4779&user=667558


by __dragon_ @ 2024-02-01 11:45:58

AC


by __dragon_ @ 2024-02-01 11:46:26

orz orz


by yuyc @ 2024-02-01 11:51:05

函数没返回值


by yuyc @ 2024-02-01 11:52:43

dijkstra 应该是void吧


by herselfqwq @ 2024-02-01 11:54:05

int dijkstra.


by __dragon_ @ 2024-02-02 10:11:13

orz orz


|