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。。。