求助,全部 TLE

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

Pig_py @ 2022-04-29 10:54:00

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define itn int 
using namespace std;
int n,m,s;
struct code{
    int to,nxt,w;
}e[500005];
int h[200005],cnt=0,dis[100005];
int vis[100005];
void add(int x,int y,int w){
    cnt++;
    e[cnt].to=y;
    e[cnt].nxt=h[x];
    h[x]=cnt;
    e[cnt].w=w;
}
void dij(int s){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        vis[i]=0;
    }
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    pq.push(make_pair(0,s));
    while(!pq.empty()){
        int x=pq.top().second;
        pq.pop();
        if(!vis[x]){
            vis[x]=1;
            for(int i=h[x];i;i=e[i].to ){
                if(!vis[e[i].to]&&dis[e[i].to ]>dis[x]+e[i].w ){
                    dis[e[i].to]=dis[x]+e[i].w;
                    pq.push(make_pair(dis[e[i].to],e[i].to ));
                }
            }
        }
    }   
}
int main(){
    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);
        add(u,v,w);
    }
    dij(s);
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}    

by Pig_py @ 2022-04-29 10:58:05

问题已解决,我是小丑终帖。


|