求调,不知道错哪里了会RE,这代码交标准版都过了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int cnt=0,head[N],n,m,s,dis[N];
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct edge{
int to,nxt,w;
}e[M];
void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dijkstra(int s){
for(int i=1;i<=n;i++)dis[i]=2e9;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
while(!q.empty()&&(q.top().first)>dis[q.top().second])q.pop();
if(q.empty())return;
int u=q.top().second;
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
int main(){
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);
for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}