# [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];
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(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)
{
}
int spfa()
{
int i,j,u,v,w;
while (!q.empty()) q.pop_front();
dis[1]=0;used[1]=true;q.push_back(1);
while (!q.empty())
{
u=q.front();q.pop_front();
used[u]=false;
{
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()
{
while (t--)
{
init();
cnt=0;
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++)
{