HDU - 4725_The Shortest Path in Nya Graph

The Shortest Path in Nya Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this paragraph, just move on.

The Nya graph is an undirected graph with "layers". Each node in the graph belongs to a layer, there are N nodes in total.

You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.

Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.

Help us calculate the shortest path from node 1 to node N.

Input

The first line has a number T (T <= 20) , indicating the number of test cases.

For each test case, first line has three numbers N, M (0 <= N, M <= 105) and C(1 <= C <= 103), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.

The second line has N numbers li (1 <= li <= N), which is the layer of ith node belong to.

Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 104), which means there is an extra edge, connecting a pair of node u and v, with cost w.

Output

For test case X, output "Case #X: " first, then output the minimum cost moving from node 1 to node N.

If there are no solutions, output -1.

Sample Input

2

3 3 3

1 3 2

1 2 1

2 3 1

1 3 3

3 3 3

1 3 2

1 2 2

2 3 2

1 3 4

Sample Output

Case #1: 2

Case #2: 3

题意：有n个点，m条通路，每个点到相邻的层需要w权值，告诉每个点所在的层数，每条通路连接的点及权值，1到n点的最小权值。

题解：最短路问题，因为数据量问题所以用dijstral算法+优先队列。

难点在于如何解决每个点到相邻的通路解决问题，注意如果这一层没有点是不用考虑的。

我在每一个点加了一个对应的虚拟点，其他相邻的层的点到虚拟点的距离为w，虚拟点到这个点的距离为0，这样就实现了相邻层到达的问题。

另外这个题目数组大小问题，因为加了点的问题，建议点的数目是题目给的两倍以上，路的数目是题目给的五倍以上。

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <queue>

using namespace std;

const int INF = 1e9+7;

const int maxn = 500050;

struct node

{

    int u,w;

    node(int a,int b):u(a),w(b){}

    bool operator <(const node &q)const

    {

        return w>q.w;

    }

};

struct edge

{

    int to,w,next;

}s[maxn];

int num,head[maxn],m,n;

int f[maxn],a[maxn],dis[maxn];

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

{

    s[num].to = v;

    s[num].w = w;

    s[num].next = head[u];

    head[u] = num++;

}

void dij()

{

    priority_queue<node> q;

    memset(f,0,sizeof(f));

    int i,u,v,w;

    for(i=0;i<=2*n;i++)

        dis[i] = INF;

    dis[1] = 0;

    q.push(node(1,0));

    while(!q.empty())

    {

        node t1 = q.top();

        q.pop();

        u = t1.u;

        if(f[u])

            continue;

        f[u] = 1;

        for(i=head[u];i!=-1;i=s[i].next)

        {

            v = s[i].to;

            w = s[i].w;

            if(f[v])

                continue;

            if(dis[u]+w<dis[v])

            {

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

                q.push(node(v,dis[v]));

            }

        }

    }

    if(dis[n]==INF)

        printf("-1\n");

    else

        printf("%d\n",dis[n]);

}

int main()

{

    int t,i,k=1,u,v,w,x;

    scanf("%d",&t);

    while(t--)

    {

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

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

        memset(f,0,sizeof(f));

        num = 0;

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

        {

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

            f[a[i]] = 1;

        }

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

        {

            if(a[i]==1)/*如果是第一层的话只要链接上一层就可以了*/

            {

                add(a[i]+n,i,0);

                if(f[a[i]+1]&&a[i]<n)

                    add(i,a[i]+n+1,x);

            }

            else if(a[i]==n)/*如果是第n层的话只要链接下一层就可以了*/

            {

                add(a[i]+n,i,0);

                if(f[a[i]-1]&&a[i]>1)

                    add(i,a[i]+n-1,x);

            }

            else

            {

                add(a[i]+n,i,0);

                if(f[a[i]-1]&&a[i]>1)

                    add(i,a[i]+n-1,x);

                if(f[a[i]+1]&&a[i]<n)

                    add(i,a[i]+n+1,x);

            }

        }

        for(i=0;i<m;i++)

        {

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

            add(u,v,w);

            add(v,u,w);

        }

        printf("Case #%d: ",k++);

        dij();

//        for(i=head[1];i!=-1;i=s[i].next)

//        {

//            printf("%d %d\n",s[i].to,s[i].w);

//        }

    }

    return 0;

}

巴特西