TLE求条

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

MineImpact_QWQ @ 2024-08-10 15:40:11

    #include<bits/stdc++.h>
    using namespace std;
    struct edge{
        int v,w;
    };
    int n,m,s;
    vector<edge> g[100100];
    int dis[100100];
    struct node{
        int num,dis;
    };
    bool operator<(node a,node b){
        return a.dis>b.dis;
    }
    priority_queue<node> q;
    int vis[100100];
    void dijkstra(){
        for(int i=1;i<=n;i++) dis[i]=INT_MAX;
        dis[s]=0;
        q.push({s,0});
        while(!q.empty()){
            node tmp=q.top();
            int u=tmp.num;
            if(vis[u]) continue;
            vis[u]=1;
            for(int i=0;i<g[u].size();i++){
                int v=g[u][i].v,w=g[u][i].w;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push({v,dis[v]});
                }
            }
        }
    }
    int main(){
        cin>>n>>m>>s;
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            g[u].push_back({v,w});
        }
        dijkstra();
        for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
        return 0;
    }

by MineImpact_QWQ @ 2024-08-10 15:40:48

用的C++14


by Hagasei @ 2024-08-10 15:43:39

应在 22 行后添加 q.pop();


by MineImpact_QWQ @ 2024-08-10 15:45:12

@Hagasei 已过谢大佬


|