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.

InputThe 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 5) and C(1 <= C <= 10 3), 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 4), which means there is an extra edge, connecting a pair of node u and v, with cost w.OutputFor 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，可以自己模拟下

所以我们采用用两个点来表示，一个是出，一个是入。

N个点，然后有N层，要假如2*N个点。

总共是3*N个点。

 

点1~N就是对应的实际的点1~N.  要求的就是1到N的最短路。

 

然后点N+1 ~ 3*N 是N层拆出出来的点。

第i层，入边到N+2*i-1, 出边从N+2*i 出来。（1<= i <= N）

 

N + 2*i    到  N + 2*(i+1)-1 加边长度为C. 表示从第i层到第j层。

N + 2*(i+1) 到 N + 2*i - 1 加边长度为C,表示第i+1层到第j层。

 

如果点i属于第u层，那么加边 i -> N + 2*u -1         N + 2*u ->i  长度都为0

 

每一层的出点和该层的每个点相连，同时该层的每个点和这一层的入点相连。第i层的入点和i+1层的出点相连，i+1层的入点和第i层的出点相连

 

可以用SPFA双端队列

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <set>
  8 #include <map>
  9 #include <string>
 10 #include <math.h>
 11 #include <stdlib.h>
 12 #include <time.h>
 13 using namespace std;
 14 
 15 #define INF 0x3f3f3f3f
 16 #define MAXN 1000100
 17 #define LL long long
 18 using namespace std;
 19 
 20 struct Edge{
 21     int to;
 22     int next;
 23     int val;
 24 }edge[MAXN];
 25 
 26 
 27 int res;
 28 int head[MAXN];
 29 int dist[MAXN];
 30 bool vis[MAXN];
 31 
 32 void init()
 33 {
 34     memset(head,-1, sizeof(head));
 35     res = 0;
 36 }
 37 
 38 void add(int u,int v,int w)
 39 {
 40     edge[res].to = v;
 41     edge[res].val = w;
 42     edge[res].next = head[u];
 43     head[u] = res++;
 44 }
 45 
 46 void SPFA(int n)
 47 {
 48     memset(vis,false,sizeof(vis));
 49     for (int i=1;i<=n;i++)
 50         dist[i]=INF;
 51     dist[1] = 0;
 52     vis[1] = true;
 53     deque<int > q;
 54     q.push_back(1);
 55     while (!q.empty())
 56     {
 57         int now = q.front();
 58         q.pop_front();
 59         vis[now] = false;
 60         for (int i=head[now];i!=-1;i=edge[i].next)
 61         {
 62             int v = edge[i].to;
 63             if (dist[v]>dist[now]+edge[i].val) {
 64                 dist[v] = dist[now] + edge[i].val;
 65                 if (!vis[v])
 66                 {
 67                     if (dist[v]<dist[q.front()])
 68                         q.push_front(v);
 69                     else
 70                         q.push_back(v);
 71                     vis[v] = true;
 72                 }
 73             }
 74         }
 75     }
 76 }
 77 
 78 
 79 
 80 int main()
 81 {
 82     int T,m,c,n;
 83     scanf("%d",&T);
 84     int t = 1;
 85     while (T--)
 86     {
 87         scanf("%d%d%d",&n,&m,&c);
 88         init();
 89         int u,v,w;
 90         for (int i=1;i<=n;i++) //同楼层
 91         {
 92             scanf("%d",&u);
 93             add(i,n+2*u-1,0);
 94             add(n+2*u,i,0);
 95         }
 96         for (int i=1;i<n;i++) // 不同楼层
 97         {
 98             add(n+2*i-1,n+2*(i+1),c);
 99             add(n+2*(i+1)-1,n+2*i,c);
100         }
101         while (m--)
102         {
103             scanf("%d%d%d",&u,&v,&w);
104             add(u,v,w);
105             add(v,u,w);
106         }
107         SPFA(3*n);
108         if (dist[n] == INF)
109             dist[n] = -1;
110         printf("Case #%d: %d\n",t++,dist[n]);
111     }
112     return 0;
113 }

 

这里推荐用Dj+优先队列

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <set>
  8 #include <map>
  9 #include <string>
 10 #include <math.h>
 11 #include <stdlib.h>
 12 #include <time.h>
 13 using namespace std;
 14 
 15 /*
 16  * 使用优先队列优化Dijkstra算法
 17  * 复杂度O(ElogE)
 18  * 注意对vector<Edge>E[MAXN]进行初始化后加边
 19  */
 20 const int INF=0x3f3f3f3f;
 21 const int MAXN=1000010;
 22 struct qnode
 23 {
 24     int v;
 25     int c;
 26     qnode(int _v=0,int _c=0):v(_v),c(_c){}
 27     bool operator <(const qnode &r)const
 28     {
 29         return c>r.c;
 30     }
 31 };
 32 struct Edge
 33 {
 34     int v,cost;
 35     Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
 36 };
 37 vector<Edge>E[MAXN];
 38 bool vis[MAXN];
 39 int dist[MAXN];
 40 void Dijkstra(int n,int start)//点的编号从1开始
 41 {
 42     memset(vis,false,sizeof(vis));
 43     for(int i=1;i<=n;i++)dist[i]=INF;
 44     priority_queue<qnode>que;
 45     while(!que.empty())que.pop();
 46     dist[start]=0;
 47     que.push(qnode(start,0));
 48     qnode tmp;
 49     while(!que.empty())
 50     {
 51         tmp=que.top();
 52         que.pop();
 53         int u=tmp.v;
 54         if(vis[u])continue;
 55         vis[u]=true;
 56         for(int i=0;i<E[u].size();i++)
 57         {
 58             int v=E[tmp.v][i].v;
 59             int cost=E[u][i].cost;
 60             if(!vis[v]&&dist[v]>dist[u]+cost)
 61             {
 62                 dist[v]=dist[u]+cost;
 63                 que.push(qnode(v,dist[v]));
 64             }
 65         }
 66     }
 67 }
 68 void addedge(int u,int v,int w)
 69 {
 70     E[u].push_back(Edge(v,w));
 71 }
 72 
 73 int main()
 74 {
 75     //freopen("in.txt","r",stdin);
 76     //freopen("out.txt","w",stdout);
 77     int T;
 78     int N,M,C;
 79     scanf("%d",&T);
 80     int iCase = 0;
 81     while(T--)
 82     {
 83         scanf("%d%d%d",&N,&M,&C);
 84         for(int i = 1;i <= 3*N;i++) E[i].clear();
 85         int u,v,w;
 86         for(int i = 1;i <= N;i++)
 87         {
 88             scanf("%d",&u);
 89             addedge(i,N + 2*u - 1,0);
 90             addedge(N + 2*u ,i,0);
 91 
 92         }
 93         for(int i = 1;i < N;i++)
 94         {
 95             addedge(N + 2*i-1,N + 2*(i+1),C);
 96             addedge(N + 2*(i+1)-1,N + 2*i,C);
 97         }
 98         while(M--)
 99         {
100             scanf("%d%d%d",&u,&v,&w);
101             addedge(u,v,w);
102             addedge(v,u,w);
103         }
104         Dijkstra(3*N,1);
105         iCase++;
106         if(dist[N] == INF)dist[N] = -1;
107         printf("Case #%d: %d\n",iCase,dist[N]);
108 
109     }
110     return 0;
111 }