# [HDU4725]The Shortest Path in Nya Graph

## 描述 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.

## 输入格式 InputFormat

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.

## 输出格式 OutputFormat

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.

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

Case #1: 2
Case #2: 3

## 来源 Source

2013 ACM/ICPC Asia Regional Online —— Warmup2

HDU 4725

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=200005;
struct edge
{
int to,next,val;
}e[10*maxn];
int head[maxn],dis[maxn],a[maxn];
bool used[maxn],b[maxn];
int i,j,t,n,m,l,r,k,z,y,x,c,cnt,ans;
deque <int> q;
inline void read(int &s)
{
s=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
}
inline void init()
{
int i,j,t;
memset(head,0,sizeof(head));
memset(b,false,sizeof(b));
memset(used,false,sizeof(used));
for (i=1;i<=n+n;i++) dis[i]=inf;
}
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
int spfa()
{
int i,j,u,v,w;
while (!q.empty()) q.pop_front();
dis=0;used=true;q.push_back(1);
while (!q.empty())
{
u=q.front();q.pop_front();
used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;
w=e[i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty())
{
if (dis[v]>dis[q.front()]) q.push_back(v);
else q.push_front(v);
}
else q.push_back(v);
}
}
}
}
return (dis[n]);
}
int main()
{
read(t);int test=0;
while (t--)
{
read(n);read(m);read(c);
init();
cnt=0;
for (i=1;i<=n;i++) read(x),a[i]=x,b[x]=true;
for (i=1;i<n;i++) if (b[i] && b[i+1])
{
ins(n+i,n+i+1,c);
ins(n+i+1,n+i,c);
}
for (i=1;i<=n;i++)
{
ins(n+a[i],i,0);
if (a[i]>1) ins(i,n+a[i]-1,c);
if (a[i]<n) ins(i,n+a[i]+1,c);
}
for (i=1;i<=m;i++)
{
read(x);read(y);read(z);
ins(x,y,z);
ins(y,x,z);
}
ans=spfa();
printf("Case #%d:",++test);
if (ans<inf) printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}``````