我用 $Dijkstra$ 算法来做这道题（加过队列优化的），但是只有 $64$ 分，求大佬指点

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
struct node{
    int v,w;
};
struct dij{
    int dis,id;
};
bool operator <(const dij &x,const dij &y){
    return x.dis<y.dis;
}
vector<node> edge[MAXN];
int n,m,dis[MAXN],s,u,v,w;
priority_queue<dij> heap;
void Dijkstra(int s) {
    fill(dis+1,dis+n+1,INT_MAX);
    dis[s]=0;
    heap.push(dij{0,s});
    while(!heap.empty()) {
        dij cur=heap.top();
        heap.pop();
        int u=cur.id;
        if(cur.dis>dis[u]) continue;
        for(auto v:edge[u]) {
            if(dis[v.v]>dis[u]+v.w) {
                dis[v.v]=dis[u]+v.w;
                heap.push(dij{dis[v.v],v.v});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        node t;
        t.v=v;
        t.w=w;
        edge[u].push_back(t);
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<" ";
    }
    return 0;
}