vector做的,就是领接表而已。加堆优化
#include<bits/stdc++.h>
#define ll register long long
#define R register
#define mod 20070707
#define maxs 0x3f3f3f3f
using namespace std;
struct node{long long v,w;};
vector<node>edge[100005];
priority_queue<pair<long long,long long> > Q;
long long dis[100005]={0};
bool vis[100005]={0};
int main(){//freopen(".in","r",stdin);freopen(".out","w",stdout);
ll n,m,s;
ll u,v,w;
scanf("%lld%lld%lld",&n,&m,&s);
for(ll i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w),edge[u].push_back((node){v,w});
}
for(ll i=1;i<=n;i++)dis[i]=2147483647;dis[s]=0;
Q.push(make_pair(s,0));
while(!Q.empty()){
pair<int,int> x=Q.top();Q.pop();
u=x.first,w=x.second;
if(dis[u]<w)continue;
for(ll i=0;i<edge[u].size();i++){
v=edge[u][i].v;
if(dis[v]>dis[u]+edge[u][i].w){
dis[v]=dis[u]+edge[u][i].w;
Q.push(make_pair(v,dis[v]));
}
}
}
for(ll i=1;i<=n;i++)printf("%lld ",dis[i]);
return 0;
}