求助TLE三个点

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

lplvvl @ 2024-11-15 23:53:39

求助

自己可以看出来是dji判断是否被访问过的问题但是,不知道错那了,求大牛

#include<bits/stdc++.h>
using namespace std;
const int Mer=1e5+10;
int head[Mer],dis[Mer];
bool vis[Mer];
struct NOde{
    int nexpointo,nexnumber,distancpo;
}a[2*Mer];
int k=0;
void ad(int u,int v,int w){
    a[k].nexnumber=head[u];
    a[k].nexpointo=v;
    a[k].distancpo=w;
    head[u]=k;
    k++;
}

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

void dji(int p){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(make_pair(0,p) );
    vis[p]=true;
    dis[p]=0;
    while(!q.empty()){
        int x=q.top().first,y=q.top().second;
        q.pop();
        vis[y]=true;
        for(int i=head[y];i!=-1;i=a[i].nexnumber){
            if(vis[a[i].nexpointo])continue; 
            if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
                q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));
                dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
            }
        }

    }
} 

int n,m,s,x,y,z; 
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        ad(x,y,z);
    }
    dji(1);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
}

就是这一段感觉出来有问题但是不会调

void dji(int p){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(make_pair(0,p) );
    vis[p]=true;
    dis[p]=0;
    while(!q.empty()){
        int x=q.top().first,y=q.top().second;
        q.pop();
        vis[y]=true;
        for(int i=head[y];i!=-1;i=a[i].nexnumber){
            if(vis[a[i].nexpointo])continue; 
            if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
                q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));
                dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
            }
        }

    }
} 

by 1nes @ 2024-11-16 10:46:52

void dji(int p){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(make_pair(0,p) );
//  vis[p]=true;
    dis[p]=0;
    while(!q.empty()){
        int x=q.top().first,y=q.top().second;
        q.pop();
        //判断
        if(vis[y])  continue;
        vis[y]=true;
        for(int i=head[y];i!=-1;i=a[i].nexnumber){
            if(vis[a[i].nexpointo])continue; 
            if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
                dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
                q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));

            }
        }

    }
} 

by 张心博harry @ 2024-12-16 18:19:43

%%%


|