51nod 1443 路径和树——最短路生成树

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1443

不只是做一遍最短路。还要在可以选的边里选最短的才行。

以为是求一遍最短路，然后按边权对边排序，哪条边两边的dis正好吻合，就把该边的边权加到ans里，把两端加到并查集里。

但其实不对。因为忽略了方向。比如如果有多个点同样地可以更新一个点，算的时候可能这多个点都因为那个点而被合到了并查集里，但其实只能有一个被合进去。

其实只要松弛点的时候如果dis[v]==dis[k]+w[i]，就把mn[v]对w[i]取min，最后把除了根的每个点的mn[ ]都算上就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

const int N=3e5+;

int n,m,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],st,mn[N];

ll dis[N],ans;

bool vis[N];

priority_queue<pair<ll,int> > q;

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void add(int x,int y,int z)

{

    to[++xnt]=y; nxt[xnt]=hd[x]; hd[x]=xnt; w[xnt]=z;

    to[++xnt]=x; nxt[xnt]=hd[y]; hd[y]=xnt; w[xnt]=z;

}

void dj()

{

    q.push(make_pair(,st));

    memset(dis,0x3f,sizeof dis); dis[st]=;

    while(q.size())

    {

        int k=q.top().second; q.pop();

        while(vis[k]&&q.size())k=q.top().second,q.pop();

        if(vis[k])break; vis[k]=;

        for(int i=hd[k],v;i;i=nxt[i])

        {

            if(dis[v=to[i]]>dis[k]+w[i])

            {

                dis[v]=dis[k]+w[i];

                q.push(make_pair(-dis[v],v));

                mn[v]=w[i];

            }

            else if(dis[v]==dis[k]+w[i])

                mn[v]=min(mn[v],w[i]);

        }

    }

}

int main()

{

    n=rdn(); m=rdn();

    for(int i=,u,v,z;i<=m;i++)

    {

        u=rdn(); v=rdn(); z=rdn(); add(u,v,z);

    }

    st=rdn();

    memset(mn,0x3f,sizeof mn);

    dj();

    for(int i=;i<=n;i++)

        if(i!=st) ans+=mn[i];

    printf("%lld\n",ans);

    return ;

}

巴特西

51nod 1443 路径和树——最短路生成树

最新文章

热门文章