P4568 [JLOI2011]飞行路线题解，也是分层图模板。

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
class node
{
	public:
		int next,len,end;
}e[5000000];
class node2
{
	public:
		int name,dis;
};
bool operator < (node2 a,node2 b)
{
	return a.dis>b.dis;
}
int head[200005]={0},cnt=0,n,m,dis[200005]={0},vis[200005]={0},k,s,en,ans=0x3f3f3f3f;
priority_queue<node2>q;
void add(int x,int y,int len)
{
	e[++cnt]=(node){head[x],len,y};
	head[x]=cnt;
}
void dijkstra(int);
int main()
{
	cin>>n>>m>>k;
	cin>>s>>en;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
        //***
		for(int j=0;j<=k-1;j++)
		{
			add(n*j+a,n*j+b,c);
			add(n*j+b,n*j+a,c);
			add(n*j+a,n*(j+1)+b,0);
			add(n*j+b,n*(j+1)+a,0);
		} 
		add(n*k+a,n*k+b,c);
		add(n*k+b,n*k+a,c);
        //***核心代码
	}
	dijkstra(s);
	for(int i=0;i<=k;i++)
		ans=min(ans,dis[i*n+en]);//坑点
	cout<<ans;
	return 0;
} 
void dijkstra(int x)//喜闻乐见的dijkstra
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[x]=vis[x]=0;
	q.push((node2){x,dis[x]});
	while(!q.empty())
	{
		int tnext=q.top().name;
		q.pop();
		vis[tnext]=1;
		for(int i=head[tnext];i;i=e[i].next) 
		{
			int tend=e[i].end;
			if(vis[tend])
				continue; 
          	if(dis[tend]>dis[tnext]+e[i].len)
          	{
          		dis[tend]=dis[tnext]+e[i].len;
				q.push((node2){tend,dis[tend]});
			}
		}
	}
	return;
}

思路

分层图啊！

for(int j=0;j<=k-1;j++)
{
	add(n*j+a,n*j+b,c);
	add(n*j+b,n*j+a,c);
	add(n*j+a,n*(j+1)+b,0);
	add(n*j+b,n*(j+1)+a,0);
} 
add(n*k+a,n*k+b,c);
add(n*k+b,n*k+a,c);