题目链接: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;
}