题目大意就是说,一共有n个点,分布在不同层,每层有一些点【有可能一层有多个点,但是同一层的点不一定直接相连】,在k层的点去k-1层和k+1层的花费都是c【即k层的点到k+1(k-1)层的每个点的花费都是c】;另外再给出m条无向边,u和v花费w【u和v可能同层也可能不同层】。求点1到点n的最小花费。
每层虚拟两个点,一个出层的点,一个入层的店,然后入点去该层的所有点花费都是0,该层所有点去出点花费都是0,然后k层出点单向去k+1层的入点和k-1层入点。【关于层与层之间的边,虽然建双向有点多此一举,可是这样做wa了。。何解??】
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #include <queue> using namespace std; const int maxn = 201010; const int maxm = 801010; const int inf = 0x3f3f3f3f; typedef struct Edge { int u, v, dis, pre; }ee; typedef struct Node { int id, dis; bool operator <(const Node &argu) const { return argu.dis < dis; } }nn; ee line[maxm]; int n, m, c, maxe, maxl; int pre[maxn], dis[maxn]; bool vis[maxn]; priority_queue<nn> q; void add_edge(int u, int v, int d) { maxe++; line[maxe].u = u; line[maxe].v = v; line[maxe].dis = d; line[maxe].pre = pre[u]; pre[u] = maxe; } void dijkstra() { nn now, next; now.id = 1, now.dis = 0; dis[1] = 0; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); if(vis[now.id]) continue; vis[now.id] = true; for(int k = pre[now.id]; k; k = line[k].pre) { if(dis[line[k].u] + line[k].dis < dis[line[k].v]) { dis[line[k].v] = dis[line[k].u] + line[k].dis; next.id = line[k].v; next.dis = dis[line[k].v]; q.push(next); } } } } int main() { // freopen("4725.in", "r", stdin); int t; scanf("%d", &t); for(int cas = 1; cas <= t; cas++) { printf("Case #%d: ", cas); scanf("%d%d%d", &n, &m, &c); int la, maxl; maxl = maxe = 0; memset(pre, 0, sizeof(pre)); memset(dis, 0x3f, sizeof(dis)); memset(vis, false, sizeof(vis)); for(int i = 1; i <= n; i++) { scanf("%d", &la); maxl = max(maxl, la); add_edge(i, n + (la << 1), 0); add_edge(n + (la << 1 | 1), i, 0); } for(int i = 1; i <= maxl; i++) { add_edge(n + (i << 1), n + ((i + 1) << 1 | 1), c); // add_edge(n + ((i + 1) << 1 | 1), n + (i << 1), c); add_edge(n + (i << 1), n + ((i - 1) << 1 | 1), c); // add_edge(n + ((i - 1) << 1 | 1), n + (i << 1), c); } int a, b, cost; for(int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &cost); add_eage(a, b, cost); add_eage(b, a, cost); } dijkstra(); if(dis[n] >= inf) printf("-1\n"); else printf("%d\n", dis[n]); } return 0; }