HDU-4725 The Shortest Path in Nya Graph( 最短路 )

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4725

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 <= 10⁵) and C(1 <= C <= 10³), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers l_i (1 <= l_i <= N), which is the layer of i^th node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 10⁴), 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

 

给若干点，分布于若干层，同层的点是不可以直接到达的，邻层的点可以相互到达，花费为c，同时给了若干无向路，求1到n的最小花费

题目难点在于建图，要将层抽象为边的关系，于是我们可以假设出2 * n个点，每层一个进点，一个出点，进点有到该层的实点和相邻层的出点到它的有向路，出点反之

本题去了一个坑点，题意上相邻层若没点是不可互通的，也就是说我们需要考虑一个无点层两侧的点的关系，但是题目所给的输入时排除了这种情况的

最后居然因为数组开小了T了好久T_T

 

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstdio>
#include<queue>
#include<stack>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 100005 * 10;

struct Edge{
    int to, val, next;
}edge[MAX];

struct Node{
    int x, d;
    Node(){}
    Node( int a, int b ) { x = a; d = b; }
    bool operator < ( const Node & a ) const{
        return d > a.d;
    }
};

int n, m, c, cnt, h[MAX], dis[MAX];

void add( int beg, int end, int val ){
    edge[cnt].to = end;
    edge[cnt].val = val;
    edge[cnt].next = h[beg];
    h[beg] = cnt;
    cnt++;
}

void dij( int start ){
    memset( dis, INF, sizeof( dis ) );
    dis[start] = 0;

    priority_queue<Node> Q;
    Q.push( Node( start, dis[start] ) );

    while( !Q.empty() ){
        Node node = Q.top(); Q.pop();
        int x = node.x;

        if( dis[x] < node.d ) continue;
        for( int k = h[x]; k != 0; k = edge[k].next ){
            int y = edge[k].to;
            if( dis[y] > dis[x] + edge[k].val ){
                dis[y] = dis[x] + edge[k].val;
                Q.push( Node( y, dis[y] ) );
            }
        }
    }
}

//层的入点为n + r
//层的出点为2 * n + r

int main(){
    int T;
    scanf( "%d", &T );
    for( int t = 1; t <= T; t++ ){
        scanf( "%d%d%d", &n, &m, &c );

        int r, beg, end, val;
        
        cnt = 1;
        memset( h, 0, sizeof( h ) );
        for( int i = 1; i <= n; i++ ){
            scanf( "%d", &r );
            add( n + r, i, 0 );
            add( i, n * 2 + r, 0 );
        }
        for( int i = 0; i < m; i++ ){
            scanf( "%d%d%d", &beg, &end, &val );
            add( beg, end, val );
            add( end, beg, val );
        }
        for( int i = 1; i < n; i++ ){
            add( n * 2 + i, n + i + 1, c );
            add( n * 2 + i + 1, n + i, c );
        }

        dij( 1 );

        cout << "Case #" << t << ": ";
        if( dis[n] == INF ) cout << -1 << endl;
        else cout << dis[n] << endl;
    }

    return 0;
}