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个点被分割为若干层,每一层之内的点不相连,x层内的所有点和x+1层内所有点的距离全部以长度c无向连接,随后有m条额外的边,依次输入两点以及权值,最后求1~n的最短路。
建图时用n + 1~2 * n和2 * n + 1 ~ 3 * n分别表示层级关系有向入边和有向出边,将权值设置为相应的c或0。
图建好以后用堆优化的迪杰斯特拉跑一遍1~n的最短路输出即可。

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

struct connect {
    int v;
    int dis;
    bool operator < (const connect &a)const {
        return dis > a.dis;
    }
};

int t;
int n, m, c;
int dis[maxn];
bool vis[maxn];
vector<connect> Adj[maxn];

void build_edge(int u, int v, int dis) {
    connect add;
    add.v = v;
    add.dis = dis;
    Adj[u].push_back(add);
}

void Dijkstra() {
    mem(dis, INF);
    mem(vis, 0);
    dis[1] = 0;
    priority_queue<connect> que;
    connect temp_push;
    temp_push.v = 1;
    temp_push.dis = 0;
    que.push(temp_push);
    while (!que.empty()) {
        connect keep = que.top();
        que.pop();
        int v = keep.v;
        if (dis[v] < keep.dis || vis[v]) {
            continue;
        }
        if (v == n) {
            return;
        }
        vis[v] = 1;
        for (int i = 0; i < Adj[v].size(); ++i) {
            connect e = Adj[v][i];
            if (!vis[e.v] && dis[e.v] > dis[v] + e.dis) {
                dis[e.v] = dis[v] + e.dis;
                //cout << "dis[" << e.v << "]=" << dis[e.v] << endl;
                connect keep_add;
                keep_add.v = e.v;
                keep_add.dis = dis[e.v];
                que.push(keep_add);
            }
        }
    }
}

int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    scanf("%d",&t);
    //cin >> t;
    for (int u = 1; u <= t; ++u) {
        scanf("%d%d%d",&n,&m,&c);
        //cin >> n >> m >> c;
        for (int i = 1; i <= n; ++i) {
            int temp;
            scanf("%d",&temp);
            //cin >> temp;
            build_edge(i, n + temp, c);
            build_edge(2 * n + temp, i, 0);
            if (--temp) {
                build_edge(n + temp, i, 0);
                build_edge(i, 2 * n + temp, c);
            }
        }
        for (int i = 1; i <= m; ++i) {
            int extra_u, extra_v, extra_dis;
            //cin >> extra_u >> extra_v >> extra_dis;
            scanf("%d%d%d",&extra_u,&extra_v,&extra_dis);
            build_edge(extra_u, extra_v, extra_dis);
            build_edge(extra_v, extra_u, extra_dis);
        }
        Dijkstra();
        //cout << "Case #" << u << ": ";
        if (dis[n] == INF) {
            dis[n] = -1;
        }
        printf("Case #%d: %d\n",u,dis[n]);
        for (int i = 1; i <= 3 * n; ++i) {
            Adj[i].clear();
        }
    }
    return 0;
}

PS.cin&&cout无限TLE。。。