标准版过了弱化版没过?
查看原帖
标准版过了弱化版没过?
85203
鱼书楼主2020/11/5 21:40

用的堆优化的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]<<' ';
}
2020/11/5 21:40
加载中...