题意：
这是一个非常容易解决的问题，您的任务只是计算图像，而仅是计算干草成本和算法成本。如果您不懂此段话，请继续。
Nya图是具有“层”的无向图。图中的每个节点都属于一个层，总共有N个节点。
您可以以成本C从x层中的任何节点移动到x + 1层中的任何节点，因为道路是双向的，因此也可以以相同的成本从x + 1层移动到x层。
此外，还有M个额外的边，每个边连接一对节点u和v，成本为w。
帮助我们计算从节点1到节点N的最短路径。
题解：
主要是建图。
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 出来。
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
不能用spfa算法搞，会超时，用堆优化的dijsktra算法。
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=1e6+10; const int inf=1e9; int N,M,C; struct node { int u; int v; int w; int next; }edge[maxn]; int head[maxn]; int tol=0; void addedge (int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } int d[maxn]; int visit[maxn]; struct qnode { int v; int w; bool operator < (const qnode &r) const { return w>r.w; } }; void dijkstra (int s) { memset(visit,0,sizeof(visit)); for (int i=1;i<=N*3;i++) d[i]=inf; priority_queue<qnode> q; d[s]=0; q.push({s,0}); qnode tmp; while (!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if (visit[u]) continue; visit[u]=1; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (!visit[v]&&d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; q.push({v,d[v]}); } } } } int main () { int T; scanf("%d",&T); for (int k=1;k<=T;k++) { scanf("%d%d%d",&N,&M,&C); memset(head,-1,sizeof(head)); tol=0; for (int i=1;i<=N;i++) { int x; scanf("%d",&x); addedge(i,N+2*x-1,0); addedge(N+2*x,i,0); } for (int i=1;i<N;i++) { addedge(N+2*i-1,N+2*(i+1),C); addedge(N+2*(i+1)-1,N+2*i,C); } while (M--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(1); if (d[N]==inf) d[N]=-1; printf("Case #%d: %d ",k,d[N]); } return 0; }