48分tle求助

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

son_of_bithch @ 2023-08-04 09:22:54

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int maxn=1e5+5,maxm=2e5+5,Inf=0x3f3f3f3f;
int n,m,s,head[maxm<<1],len;
bool vis[maxn];
long long int dis[maxn];
struct Edge{
    int u,v,w,next;
}e[maxm<<1];
struct Node{
    int num,dis;
    Node(int x,int y){
        num=x;dis=y;
    }
};
bool operator<(const Node &a,const Node &b){
    return a.dis>b.dis;
}
void Dij(int s){
    priority_queue<Node> q;
    memset(dis,Inf,sizeof(dis));
    dis[s]=0;
    q.push(Node(s,0));
    while(!q.empty()){
        int u=q.top().num;q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(Node(v,dis[v]));
            }
        }
    }
}
void Insert(int u,int v,int w){
    e[++len].u=u;
    e[len].v=v;
    e[len].w=w;
    e[len].next=head[u];
    head[u]=len;
}
void Read(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Insert(u,v,w);
    }
}
int main(){
    Read();
    Dij(s);
    for(int i=1;i<=n;++i){
        printf("%lld ",dis[i]);
    }
    return 0;
}

by Michaellg @ 2023-08-04 09:42:29

@son_of_bithch 要使用 vis 数组

我的代码:

while (!q.empty()) {
    int u = q.top().u; q.pop();
    if (vis[u])
        continue;
    vis[u] = true;
    for (int i = h[u]; i; i = r[i].nxt)
        if (dis[u] + r[i].dis < dis[r[i].v]) {
            dis[r[i].v] = dis[u] + r[i].dis;
            q.push(node{r[i].v, dis[r[i].v]});
        }
}

by son_of_bithch @ 2023-08-04 10:04:40

@Michaellg 蟹蟹大佬


|