hdu 4725 The Shortest Path in Nya Graph（建图+优先队列dijstra）

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

题意：有n个点和n层，m条边，每一层的任意一个点都可以花费固定的值到下一层或者上一层的任意点

然后m条边链接的点可以花费给出的值进行转移，最后问从i点到n点最少要花费多少。

这题点的个数有100000，层数也是100000，不算额外边暴力建边肯定要爆。

所以可以把层数也当成一个点比如说i点在j层于是n+j就与i链接花费0然后i点可以和上下层任意一个点链接

及i与n+j+1链接i与n+j-1链接花费为c，最后额外边就正常处理。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stdio.h>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 1e5 + 10;
int n , m , c , u , v , w , l , pos[M << 1] , dis[M << 1];
struct qnode {
    int v , w;
    qnode(int v , int w):v(v) , w(w) {
        
    }
    bool operator <(const qnode &r) const{
        return w > r.w;
    }
};
struct TnT {
    int v , w , next;
    TnT(int v , int w):v(v) , w(w) {
        
    }
};
vector<TnT> vc[M << 1];
void add(int u , int v , int w) {
    vc[u].push_back(TnT(v , w));
}
bool vis[M << 1];
void dij(int sta) {
    priority_queue<qnode>q;
    for(int i = 1 ; i <= 2 * n ; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    dis[sta] = 0;
    q.push(qnode(sta , 0));
    while(!q.empty()) {
        int u = q.top().v;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i = 0 ; i < vc[u].size() ; i++) {
            TnT gg = vc[u][i];
            if(dis[gg.v] > dis[u] + gg.w && !vis[gg.v]) {
                dis[gg.v] = dis[u] + gg.w;
                q.push(qnode(gg.v , dis[gg.v]));
            }
        }
    }
}
int main() {
    int t , ans = 0;
    scanf("%d" , &t);
    while(t--) {
        ans++;
        scanf("%d%d%d" , &n , &m , &c);
        for(int i = 1 ; i <= 2 * n ; i++) {
            
            vc[i].clear();
        }
        for(int i = 1 ; i <= n ; i++) {
            vis[i] = false;
        }
        for(int i = 1 ; i <= n ; i++) {
            scanf("%d" , &l);
            pos[i] = l;
            vis[l] = true;
        }
        for(int i = 1 ; i <= n ; i++) {
            if(pos[i] == 1) {
                add(pos[i] + n , i , 0);
                if(n > 1 && vis[pos[i] + 1]) {
                    add(i , pos[i] + 1 + n , c);
                }
            }
            else if(pos[i] == n) {
                add(pos[i] + n , i , 0);
                if(n > 1 && vis[pos[i] - 1]) {
                    add(i , pos[i] - 1 + n , c);
                }
            }
            else {
                add(pos[i] + n , i , 0);
                if(1 < n && vis[pos[i] + 1]) {
                    add(i , pos[i] + 1 + n , c);
                }
                if(n > 1 && vis[pos[i] - 1]) {
                    add(i , pos[i] - 1 + n , c);
                }
            }
        }
        for(int i = 1 ; i <= m ; i++) {
            scanf("%d%d%d" , &u , &v , &w);
            add(u , v , w);
            add(v , u , w);
        }
        dij(1);
        if(dis[n] == inf)
            dis[n] = -1;
        printf("Case #%d: %d
" , ans , dis[n]);
    }
    return 0;
}