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.
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.
题意就是求最短路问题，但是有一个层的概念，刚开始的时候是想着把相邻两层之间的每一点都再连一条边，但是这样的复杂度可以到达 n^2 ，比如在相邻两层上都有 n/2 个点。
然后百度了之后，发现是要增加点，表示每一层，这个点和同层的连边的边权为0，这样的话两层之间就只需要再加一条边，但是这样还有一个问题，就是同层点之间来往的话，应该是到达相邻的层然后再回来，所以需要在每一层增加两点，分别表示入的和出的。。。
还有一个坑点，就是如果某一层没有点的话，是不能与相邻层连线的。。。
代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h> using namespace std; const int MaxN=*;
const int MaxM=*;
const int INF=10e9+; struct Edge
{
int to,next,cost;
}; struct Node
{
int v,val; Node(int _v=,int _val=):v(_v),val(_val) {} bool operator < (const Node &a) const
{
return val>a.val;
}
}; Edge E[MaxM];
int head[MaxN],Ecou; void init(int N)
{
Ecou=; for(int i=;i<=N;++i)
head[i]=-;
} void addEdge(int u,int v,int c)
{
E[Ecou].to=v;
E[Ecou].cost=c;
E[Ecou].next=head[u];
head[u]=Ecou++;
} bool vis[MaxN]; void Dijkstra(int lowcost[],int N,int start)
{
priority_queue <Node> que;
Node temp;
int u,v,c;
int len; for(int i=;i<=N;++i)
{
lowcost[i]=INF;
vis[i]=;
} lowcost[start]=;
que.push(Node(start,)); while(!que.empty())
{
temp=que.top();
que.pop(); u=temp.v; if(vis[u])
continue; vis[u]=; for(int i=head[u];i!=-;i=E[i].next)
{
v=E[i].to;
c=E[i].cost; if(!vis[v] && lowcost[v]> lowcost[u]+c)
{
lowcost[v]=lowcost[u]+c;
que.push(Node(v,lowcost[v]));
}
}
}
} int ans[MaxN];
bool have[MaxN]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); int T;
int N,M,C;
int u,v,c;
int cas=; scanf("%d",&T); while(T--)
{ scanf("%d %d %d",&N,&M,&C); init(*N);
memset(have,,sizeof(have)); for(int i=;i<=N;++i)
{
scanf("%d",&u); addEdge(i,N+*u-,);
addEdge(N+*u,i,); have[u]=;
} for(int i=;i<N;++i)
if(have[i] && have[i+])
{
addEdge(N+*i-,N+*(i+),C);
addEdge(N+*(i+)-,N+*i,C);
} for(int i=;i<=M;++i)
{
scanf("%d %d %d",&u,&v,&c); addEdge(u,v,c);
addEdge(v,u,c);
} Dijkstra(ans,*N,); printf("Case #%d: %d\n",cas++,ans[N]==INF ? - : ans[N]);
} return ;
}