堆优化+dijkstra 怎么没过 求助大佬
#include<bits/stdc++.h>
using namespace std;
#define PII pair<long long,int>
int n,m,start;
int to[200001],nex[200001],last[100001],cnt;
long long len[200001],dis[100001];
bool vis[100001];
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int a,int b,int c){
cnt++;
to[cnt]=b;
len[cnt]=c;
nex[cnt]=last[a];
last[a]=cnt;
}
int main(){
scanf("%d %d %d",&n,&m,&start);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
dis[u]=dis[v]=INT_MAX;
add(u,v,w);
}
dis[start]=0;
PII t;
t.first=0,t.second=start;
q.push(t);
while(!q.empty()){
t=q.top();
q.pop();
int point=t.second,weigh=t.first;
if(vis[point]) continue;
vis[point]=1;
int i=last[point];
while(i!=0){
int go=to[i];
if(dis[go]>dis[point]+len[i]){
dis[go]=dis[point]+len[i];
t.first=dis[go],t.second=go;
q.push(t);
}
i=nex[i];
}
}
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
}
Thanks♪(・ω・)ノ