题目链接：传送门

The Shortest Path in Nya Graph

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6804    Accepted Submission(s): 1535 Problem 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.   Input 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 <= 10 ⁵) and C(1 <= C <= 10 ³), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers. The second line has N numbers l _i (1 <= l _i <= N), which is the layer of i ^th node belong to. Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 10 ⁴), which means there is an extra edge, connecting a pair of node u and v, with cost w.   Output 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.   Sample Input 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   Sample Output Case #1: 2 Case #2: 3

解题思路：一开始没想太多，自以为同一层中点的距离为0，结果根本只是我自己的意淫，wa了n次，后来果断看了一些大牛博客，顿时明白过来。

将每一层都抽象成一个点，每一层与该层的店之间不能建立双向边，否则同一层中的点的距离还是0。层与点间建立单向边，点与相邻层间建立单向边，都含有点的相邻层间建立双向边。

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <stack> #include <queue> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N = 200009; const int M = 1000; const int INF = 0x3fffffff; //将每一层都抽象成一个点，编号为N+1到2N struct Edge{ int node,len; Edge*next; }m_edge[N*4]; Edge*head[N]; int dist[N],vis[N],Ecnt; int lay[N],flag[N]; void init() { Ecnt = 0; fill( head , head+N , (Edge*)0 ); fill( flag , flag+N , 0 ); } void mkEdge( int a , int b , int c ) { m_edge[Ecnt].node = b; m_edge[Ecnt].len = c; m_edge[Ecnt].next = head[a]; head[a] = m_edge+Ecnt++; } void spfa() { fill( dist , dist+N , INF ); fill( vis , vis+N , 0 ); queue<int>point; point.push(1); vis[1] = 1; dist[1] = 0; while( !point.empty() ){ int s = point.front(); point.pop(); vis[s] = 0; for( Edge*p = head[s] ; p ; p = p->next ){ int t = p->node; if( dist[t] > dist[s]+p->len ){ dist[t] = dist[s]+p->len; if( !vis[t] ){ point.push(t); vis[t] = 1; } } } } } int main() { int T,cas = 0; scanf("%d",&T); while( T-- ){ init(); int n,m,c; scanf("%d%d%d",&n,&m,&c); for( int i = 1 ; i <= n ; ++i ){ scanf("%d",&lay[i]); flag[lay[i]] = 1; } //层与层之间建边 for( int i = 1 ; i < n ; ++i ){ if( flag[i]&&flag[i+1] ){ mkEdge(n+i,n+i+1,c); mkEdge(n+i+1,n+i,c); } } //层到点单向建边，点到相邻层单向建边 for( int i = 1 ; i <= n ; ++i ){ mkEdge( n+lay[i] , i , 0 ); if( lay[i] > 1 ){ mkEdge( i , n+lay[i]-1 , c ); } if( lay[i] < n ){ mkEdge( i , n+lay[i]+1 , c ); } } int u,v,L; //点与点间建立双向边 for( int i = 0 ; i < m ; ++i ){ scanf("%d%d%d",&u,&v,&L); mkEdge( u , v , L ); mkEdge( v , u , L ); } spfa(); int ans = dist[n]; if( ans == INF ) ans = -1; printf("Case #%d: %d\n",++cas,ans); } return 0; }