题目大意：一共有n层平面，每一层平面都有一定数目的点（也有可能某一层没有点），从x层到x+1层和从x+1层到x层的花费均为c，除此之外，还有m条边，不同层之间的点也有可能有边，每一条边都有一定的花费，然后问从1到n的最少花费？
题解：这个题主要是构图，构图方法有两种。
方法1：将每一层平面看成一个点，这个点可通过加+n来获得。然后该怎么连接的？
假设第x层有点a,b,c。将x+n和a,b,c相连接（有向边），然后在把a,b,c再和x-1层和x+1层面相连。这样对于每一层的任何一个点都可以通过先到达另外一层的平面上，然后再通过该平面到达该平面上的点。
#include<bits/stdc++.h> using namespace std; const int N=1e6+7; const int inf=0x3f3f3f3f; int head[N],cnt=0; int arr[N]; struct stu{ int to,nxt; int weight; }edge[N]; bool inq[N]; int dis[N]; int cas=0; void add(int x,int y,int weight){ edge[cnt].to=y; edge[cnt].nxt=head[x]; edge[cnt].weight=weight; head[x]=cnt++; } void SPFA(){ memset(dis,inf,sizeof(dis)); memset(inq,0,sizeof(inq)); queue<int>Q; Q.push(1); inq[1] = 1; dis[1] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = head[u];i != -1;i = edge[i].nxt){ int v = edge[i].to,w = edge[i].weight; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; if(!inq[v]){ Q.push(v); inq[v] = 1; } } } } } void solve(){ cnt=0; memset(head,-1,sizeof head); int n,m,c; scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=n;i++) { scanf("%d",&arr[i]); add(arr[i]+n,i,0); } for(int i=1;i<=n;i++){ if(arr[i]>1){ add(i,arr[i]+n-1,c); } if(arr[i]<n){ add(i,arr[i]+n+1,c); } } for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } SPFA(); if(dis[n] == inf) printf("Case #%d: -1 ",++cas); else printf("Case #%d: %d ",++cas,dis[n]); } int main(){ int t; scanf("%d",&t); while(t--) solve(); return 0; }
方法2 ：就是将每一个平面都看成两个点，一个入点，一个出点，怎么连呢？第x层的入点和x层上的没个点都相连，然后x层上的每个点再与x层上的出点连接（均为有向边,权值为0），再连平面，平面x的出点与x+1面入点相连，在于x-1面入点相连权值均为c。这样进入一个平面可以通过入点进入，走出一个平面可以通过出点走出...
代码： （粘一份别人的code，我的code一直T，QWQ）
#include <iostream> #include <string.h> #include <queue> #include <vector> #include <cmath> using namespace std; const int maxn = 3e5+5; const int MAX = 0x3f3f3f3f; vector<pair<int,int> > e[maxn]; int n,m,cost; int dist[maxn]; int dij() { priority_queue<pair<int,int> > que; memset(dist,0x3f,sizeof dist); que.push( make_pair(0,1) ); dist[1] = 0; while (!que.empty()) { int cur = que.top().second; que.pop(); for (int i=0; i<e[cur].size(); i++) { int to = e[cur][i].first; int div = e[cur][i].second; if (dist[to] > dist[cur] + div) { dist[to] = dist[cur] + div; que.push( make_pair(-dist[to],to) ); } } } return dist[n]; } int main() { // freopen("a.txt","r",stdin); int times,k=0; scanf("%d",×); while (times--) { scanf("%d%d%d",&n,&m,&cost); // 楼层抽象化成2个点,一个入点，一个出点 int temp; for (int i=1; i<=n; i++) { //i代表点,temp是该点的楼层 scanf("%d",&temp); e[temp*2+n-1].push_back( make_pair(i,0) ); // 入点指向平面的点 e[i].push_back( make_pair(temp*2+n,0) ); // 平面中的点指向出点 } // 每个点之间的边 int from,to,div; for (int i=1; i<=m; i++) { scanf("%d%d%d",&from,&to,&div); e[from].push_back( make_pair(to,div) ); e[to].push_back( make_pair(from,div)); } // 当前层的 出点 与 相邻层的 入点 建边 for (int i=1; i<=n; i++) { from = 2 * i + n; // 出点 if (i > 1) { to = from - 3; // 该层的出点,到上一层的入点 e[from].push_back( make_pair(to,cost) ); } if (i < n) { to = from + 1; // 该层的出点,到下一层的入点 e[from].push_back( make_pair(to,cost) ); } } int ans = dij(); if (ans == MAX) printf("Case #%d: -1 ",++k); else printf("Case #%d: %d ",++k,ans); for (int i=1; i<=3 * n; i++) e[i].clear(); } return 0; }