题目链接：HDU4725-The Shortest Path in Nya Graph

题意：

n点，m边的无向图，每个点会对应一个层数，层数相邻的点可以花费代价C跃迁，统一层数的点则不能相互跃迁，问1到n的最短路。

题解：

每一层对应新建一个点，然后每个层点指向属于这层的点，花费为0，然后对于每个原图上的点，指向与该点层数相邻的两个层点，花费为C，最短路即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5;
const int MAXM = 1e6;
const int inf = 0x3f3f3f3f;
int T, n, m, C;
int col[MAXN];
struct EDGE
{
    int v, w, nxt;
} edge[MAXM * 2];
int cnt, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
struct node
{
    int u;
    int d;
    node(int u, int d) : u(u), d(d) {}
    bool operator<(const node &a) const
    {
        return d > a.d;
    }
};
bool used[MAXN];
int dis[MAXN];
void dijkstra(int st)
{
    priority_queue<node> que;
    while (!que.empty())
        que.pop();
    memset(dis, inf, sizeof(dis));
    dis[st] = 0;
    que.push(node(st, dis[st]));
    memset(used, 0, sizeof(used));
    while (!que.empty())
    {
        int u = que.top().u;
        que.pop();
        if (used[u])
            continue;
        used[u] = 1;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (used[v])
                continue;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                que.push(node(v, dis[v]));
            }
        }
    }
}
int main()
{
    int icase = 0;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &C);
        memset(col, 0, sizeof(col));
        memset(fir, -1, sizeof(fir));
        memset(used, 0, sizeof(used));
        cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &col[i]);
            used[col[i]] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            addedge(col[i] + n, i, 0);
            if (col[i] == 1)
            {

                if (col[i] < n && used[col[i] + 1])
                    addedge(i, col[i] + n + 1, C);
            }
            else if (col[i] == n)
            {
                if (col[i] > 1 && used[col[i] - 1])
                    addedge(i, col[i] + n - 1, C);
            }
            else
            {
                if (col[i] < n && used[col[i] + 1])
                    addedge(i, col[i] + n + 1, C);
                if (col[i] > 1 && used[col[i] - 1])
                    addedge(i, col[i] + n - 1, C);
            }
        }
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dijkstra(1);
        if (dis[n] == inf)
            dis[n] = -1;
        printf("Case #%d: %d\n", ++icase, dis[n]);
    }
    return 0;
}