用的堆优化的dij,得了90,是不是哪里错了?
#include<iostream>
#include<queue>
using namespace std;
int cnt,hea[10000001],dis[10000001],vis[10000001],s,n,m;
struct node{
int w,to,nex;
}e[1000000];
void add(int u,int v,int w)
{
e[++cnt].w=w;
e[cnt].nex=hea[u];
hea[u]=cnt;
e[cnt].to=v;
}
void djs()
{
for(int i=1;i<=n;i++)dis[i]=1000000099;
dis[s]=0;
priority_queue<pair<int ,int> >q;
q.push(make_pair(0,s));
while(q.size())
{
int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;
for(int i=hea[u];i;i=e[i].nex)
{
int v=e[i].to;
if(dis[u]+e[i].w<dis[v])
dis[v]=dis[u]+e[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
int main()
{
int u,v,w;
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
}
djs();
for(int i=1;i<=n;i++)
cout<<dis[i]<<' ';
}