2015
09-17

# The Shortest Path in Nya Graph

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 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.

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.

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

CODE:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

#define mkp make_pair
#define fst first
#define scd second

using namespace std;
int dis[100011];
int vis[100011];
int lay[100011];
vector<int>vec[100011];
struct Edge_t{
int to,next,cap;
}edge[500000];

inline void adde(int u,int v,int w){
edge[et].to=v;
edge[et].cap=w;
}

inline void spfa(int n,int C){
queue<int>q;
q.push(1);
memset(vis,0,sizeof vis);
memset(dis,-1,sizeof dis);
dis[1]=0;
int e,u,v,size,i,k;
while(!q.empty()){
u=q.front();q.pop();
vis[u]=0;
v=edge[e].to;
if(dis[v]<0 || dis[v]>dis[u]+edge[e].cap){
dis[v]=dis[u]+edge[e].cap;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
if(lay[u]>1){
size=vec[k=(lay[u]-1)].size();
for(i=0;i<size;++i){
v=vec[k][i];
if(dis[v]<0 || dis[v]>dis[u]+C){
dis[v]=dis[u]+C;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
if(lay[u]<n){
size=vec[k=lay[u]+1].size();
for(i=0;i<size;++i){
v=vec[k][i];
if(dis[v]<0 || dis[v]>dis[u]+C){
dis[v]=dis[u]+C;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}

}
}
}

int main(){
int t,tt=0,C;
int n,m,u,v,i,size,w;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&C);
memset(vis,0,sizeof vis);
for(i=1;i<=n;++i){
scanf("%d",&lay[i]);//第i个点所以层为lay[i]
vec[i].clear();
}
while(m--){
scanf("%d%d%d",&u,&v,&w);
if(!vis[u]){//把点加入层..
vec[lay[u]].push_back(u);
vis[u]=1;
}
if(!vis[v]){
vec[lay[v]].push_back(v);
vis[v]=1;
}
}
if(!vis[1])//始点和终于一定要在某一层内..
vec[lay[1]].push_back(1);
if(!vis[n])
vec[lay[n]].push_back(n);
for(i=1;i<=n;++i)//如果某一层没有点
if(vec[lay[i]].empty())
vec[lay[i]].push_back(i);
spfa(n,C);
printf("Case #%d: %d\n",++tt,dis[n]);
}
return 0;
}