hdu-4725-The Shortest Path in Nya Graph-层次网络

我们依据每一个人的layer把同样layer的人分配到同一个层次中。

然后记录走到每一个层次的最小值。

假设这个最小值被更新了。 那么我们就更新与这个层次相连的层次上的点。

其它的就是最普通的spfa求最短路了。

只是要用优先队列优化一下。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

using namespace std;

#define maxn 110000

#define INF 99999999

struct list

{

    int next;

    int u,v,w;

} edge[maxn*2];

vector<int>vec[maxn];

struct listt

{

    int u;

    int w;

    friend bool operator <(const listt &a,const listt &b)

    {

        return a.w>b.w;

    }

} p,q;

priority_queue<struct listt>que;

int head[maxn];

int nums;

map<int,int>mp;

void init()

{

    for(int i=0; i<maxn; i++)vec[i].clear();

    memset(head,-1,sizeof(head));

    nums=1;

    while(!que.empty())que.pop();

    mp.clear();

}

void add(int u,int v,int w)

{

    edge[nums].u=u;

    edge[nums].v=v;

    edge[nums].w=w;

    edge[nums].next=head[u];

    head[u]=nums++;

}

int dis[maxn];

int minn[maxn];

int belong[maxn];

int ans[maxn];

int spfa(int st,int ed,int k)

{

    for(int i=0; i<=ed; i++)dis[i]=INF;

    for(int i=0; i<=maxn; i++)minn[i]=INF;

    p.u=st;

    p.w=0;

    que.push(p);

    dis[st]=0;

    while(!que.empty())

    {

        q=que.top();

        que.pop();

        if(q.u==ed)

        {

            return q.w;

        }

        int x=belong[q.u];

        if(q.w<minn[x])

        {

            minn[x]=q.w;

            p.w=minn[x]+k;

            if(ans[x-1]+1==ans[x])

            {

                for(int i=0; i<vec[x-1].size(); i++)

                {

                    p.u=vec[x-1][i];

                    if(dis[p.u]>p.w)

                    {

                        dis[p.u]=p.w;

                        que.push(p);

                    }

                }

            }

            if(ans[x]+1==ans[x+1])

            {

                for(int i=0; i<vec[x+1].size(); i++)

                {

                    p.u=vec[x+1][i];

                    if(dis[p.u]>p.w)

                    {

                        dis[p.u]=p.w;

                        que.push(p);

                    }

                }

            }

        }

        for(int i=head[q.u]; i!=-1; i=edge[i].next)

        {

            int v=edge[i].v;

            int w=edge[i].w;

            if(dis[v]>dis[q.u]+w)

            {

                dis[v]=dis[q.u]+w;

                p.u=v;

                p.w=dis[v];

                que.push(p);

            }

        }

    }

    return -1;

}

vector<int>all;

int main()

{

    int cas=0;

    int T,m,n,k,u,v,w;

    scanf("%d",&T);

    while(T--)

    {

        cas++;

        init();

        scanf("%d%d%d",&n,&m,&k);

        all.clear();

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

        {

            scanf("%d",&belong[i]);

            //vec[belong[i]].push_back(i);

            all.push_back(belong[i]);

        }

        //-----离散化

        sort(all.begin(),all.end());

        int st=1;

        mp[all[0]]=1;

        ans[1]=all[0];

        for(int i=1; i<all.size(); i++)

        {

            if(all[i]!=all[i-1])

            {

                mp[all[i]]=++st;

                ans[st]=all[i];

            }

        }

        //-------------------

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

        {

            int x=mp[belong[i]];

            vec[x].push_back(i);

            belong[i]=x;

        }

        for(int i=1; i<=m; i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

            add(v,u,w);

        }

        printf("Case #%d: %d\n",cas,spfa(1,n,k));

    }

    return 0;

}