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 <= 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. 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 dij的堆优化
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<cstdio> #include<vector> #include<set> #include<cstring> #include<cstdlib> #include<time.h> #include<stack> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=7e5+5; int t,n,m,c,tot,cnt,head[maxn],Next[maxn],ver[maxn],edge[maxn],p[maxn]; int d[maxn],layer[maxn]; bool jg[maxn],vis[maxn]; void init(){ memset(edge, INF, sizeof(edge)); memset(head, 0, sizeof(head)); memset(jg,0,sizeof(jg)); memset(p,0,sizeof(p)); cnt=0; } void add(int u,int v,int w) { ver[++cnt]=v; edge[cnt]=w; Next[cnt]=head[u]; head[u]=cnt; } void dij() { memset(vis,0,sizeof(vis)); priority_queue<pair<int,int>>q; memset(d,0x3f,sizeof(d)); int k=d[0]; d[1]=0; q.push(make_pair(0,1)); while(q.size()) { int x=q.top().second;q.pop(); if(vis[x])continue; for(int i=head[x];i;i=Next[i]) { int y=ver[i],z=edge[i]; if(d[y]>d[x]+z) { d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } if(k==d[n]) printf("-1\n"); else printf("%d\n",d[n]); } int main(){ int t,tot=1; cin>>t; while(t--){ init(); cin>>n>>m>>c; for(int i=1;i<=n;i++){ scanf("%d",&p[i]); p[i]+=n; jg[p[i]]=1; add(p[i],i,0); } for(int i=1;i<=n;i++){ if(jg[p[i]+1])add(i,p[i]+1,c); if(jg[p[i]-1])add(i,p[i]-1,c); } for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } printf("Case #%d: ",tot); tot++; dij(); } return 0; }