大佬们求助！！！全TLE

zhaozhicheng2010 @ 2022-08-06 17:25:01

#include<bits/stdc++.h>

using namespace std;

const long long N=100005,inf=2147483647;

long long dis[N],chack[N],n,m,s,l,r,w;

struct stu{

    long long v,w;
};

vector <stu> a[N];

  void dijkstra(long long s)
{

    for(long long i=1;i<=n;i++){
        long long k=0;
        for(long long j=1;j<=n;j++) if(!chack[j]&&dis[j]<dis[k]) k=j;
        chack[k]=1;
        for(long long j=0;j<a[k].size();j++){
            if(!chack[a[k][j].v]) dis[a[k][j].v]=min(dis[a[k][j].v],dis[k]+a[k][j].w);
        }
    }
}

  int main(){

    scanf("%lld%lld%lld",&n,&m,&s);
    for(long long i=0;i<=n;i++){
        dis[i]=inf;
    }
    for(long long i=1;i<=m;i++){
        scanf("%lld%lld%lld",&l,&r,&w);
        a[l].push_back({r,w});
    }
    dis[s]=0;
    dijkstra(s);
    for(long long i=1;i<=n;i++) printf("%lld ",dis[i]);
    return 0;
}

by i_am_a_joker @ 2022-08-06 17:34:53

堆优化

by LYM20114 @ 2022-08-06 19:51:23

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m,s;
struct nod{
    int next,w;
    bool operator <(const nod &x)const{
        return w > x.w;
    }
};
vector <nod> V[100001];
void add(int x,int y,int z){
    nod l;l.next = y;l.w = z;
    V[x].push_back(l);
}
inline void dijkstra(int x){
    long long disTo[100005];
    priority_queue <nod> pq;
    for(int i = 0;i <= n + 1;i++)
        disTo[i] = 0x7fffffff;
    pq.push((nod){s,0});
    disTo[s] = 0;
    while(!pq.empty()){
        nod px = pq.top();
        int nx = px.next;
        pq.pop();
        if(px.w != disTo[nx]) continue; 
        for(int i = 0;i < V[nx].size();i++){
            int xx = V[nx][i].next;
            if(disTo[nx] + V[nx][i].w < disTo[xx]){
                disTo[xx] = disTo[nx] + V[nx][i].w;
                pq.push((nod){xx,disTo[xx]});
            }
        }
    }
    for(int i = 1;i <= n;i++) cout << disTo[i] << " ";
    cout << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    dijkstra(s);
    return 0;
}

by zhaozhicheng2010 @ 2022-08-09 21:18:54

谢谢各位大佬，已AC；