题目大意是：
有一些点，分为几层，然后层与层之间可花费代价C到达，还有一些特殊边，使得某个点和某个点之间花费某代价可以到达，求从1到n的最小代价。
一开始的想法是，既然层与层之间可以到达，那么对于第i层和第i+1层，把第i层的所有点与第i+1层的所有点连边，权值为C，特殊的边该怎么连怎么连，然后跑最短路。
然后我看了一下数据范围——N, M (0 <= N, M <= 105) 笑不出来
好吧，那让我们考虑一下如何优化。
我们知道，同一层内的点是可以相互到达的且无花费。也就是说，如果我想去到第i层，我到达第i层的某个点后就相当于我到了这一层中所有的点。
那么对于每一层，我可以建一个入点和一个出点（或者说就建一个点也行，反正连进和连出的边的性质是一样的）。层与层之间就有建的点相连（代价就为C），层内的点全部连向建的点（代价为0）。
连变数：2*n+m 时间O（e loge）能过
注意：1.建的虚拟点的编号一定不要和原来的点重复了。2.图中的点不再是n个，而应该建成3n个
#include <cstdio> #include <vector> #include <queue> #include <cstring> #define N 100003 #define M 100003 using namespace std; int read() { int f=1,x=0;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } const int INF=0x3f3f3f3f; struct qnode { int v; int c; qnode(int _v=0,int _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const { return c>r.c; } }; struct Edge { int v,cost; Edge(int _v=0,int _cost=0):v(_v),cost(_cost){} }; vector<Edge> E[N*2+M]; bool vis[N*3]; int dist[N*3]; void dij(int n,int start)//点的编号从1开始 { memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) dist[i]=INF; priority_queue<qnode> que; while(!que.empty()) que.pop(); dist[start]=0; que.push(qnode(start,0)); qnode tmp; while(!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u]) continue; vis[u]=true; for(int i=0;i<E[u].size();i++) { int v=E[tmp.v][i].v; int cost=E[u][i].cost; if(!vis[v]&&dist[v]>dist[u]+cost) { dist[v]=dist[u]+cost; que.push(qnode(v,dist[v])); } } } } void add(int u,int v,int w) { E[u].push_back(Edge(v,w)); } int main() { int T=read(); for(int k=1;k<=T;++k) { for(int i=0;i<=N*2+M;i++) if(!E[i].empty()) E[i].clear(); int n=read(),m=read(),c=read(); for(int i=1;i<=n;++i) { int x=read(); add(x*2+n-1,i,0); add(i,x*2+n,0); } for(int i=1;i<=m;++i) { int u=read(),v=read(),w=read(); add(u,v,w);add(v,u,w); } for(int i=1;i<=n;++i) { int u=2*i+n; if(i>1)add(u,u-3,c); if(i<n)add(u,u+1,c); } dij(3*n,1); printf("Case #%d: %d\n",k,(dist[n]==INF?-1:dist[n])); } } /* */
原文：https://www.cnblogs.com/yyys-/p/11172799.html
