样例都过了
然后……
qwq
蒟蒻再此先膜众大佬为敬!
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
int to,next,v;
}tree[500005];
int n,m,h[500005],cnt,d[500005];
bool pd[500005];
struct edge
{
int num,dis;
bool operator<(const edge & t)const
{
return dis>t.dis;
}
}uytr;
void qxx(int x,int y,int z)
{
cnt++;
tree[cnt].next=h[x];
tree[cnt].to=y;
tree[cnt].v=z;
h[x]=cnt;
}
void dij(int s0)
{
memset(pd,false,sizeof(pd));
for(int i=1;i<=n;i++)d[i]=0x7fffffff/2;
d[s0]=0;
priority_queue<edge>qu;
qu.push({s0,d[s0]});
for(int i=1;i<=n;i++)
{
edge ppp=qu.top();
qu.pop();
int k=ppp.num;
pd[k]=true;
for(int j=h[k];j!=0;j=tree[j].next)
{
int y=tree[j].to;
if(pd[y]==false&&tree[j].v+d[k]<d[y])
{
d[y]=tree[j].v+d[k];
qu.push({y,d[y]});
}
}
}
}
int main()
{
int s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
qxx(x,y,z);
qxx(y,x,z);
}
dij(s);
if(d[n]==0x7fffffff/2)
{
cout<<4294967296-1;
}
for(int i=1;i<=n;i++)
cout<<d[i]<<" ";
}