这里先直接上一个题解，下午应该会有自己的打法！
/*
首先看一个问题：
在你的强力援助下，PCY 成功完成了之前的所有任务，他觉得，现在正是出去浪的大好时光。于是，他来到高速公路上，找到一辆摩的前往几千公里以外他心仪的那家黄焖鸡米饭。
由于 PCY 的品味异于常人，途经几百个城市的黄焖鸡米饭他都不屑一顾，他只愿意前往他心中最好的那家，但是为了一碗二十块钱的黄焖鸡米饭，他不愿意花上几千块的路费，他希望路费尽量少。
高速路上的警察叔叔被他的行为所打动，于是在多方协调下，最多 K 条城市之间的高速收费站愿意免费为 PCY 放行（可以任意选择）。
显然，PCY 已经筋疲力尽，不想再动用自己的数学天才来计算他可以花费的最小路费，因此他希望你可以帮他最后一次，他说他可以请你吃大碗的黄焖鸡米饭，还可以加一瓶豆奶。
现在给你 N 个城市 （编号为0 …N - 1 ），M 条道路，和每条高速公路的花费Wi ，以及题目所描述的 K。PCY 想从城市 S 到城市 T ，因为他对 T 城市的黄焖鸡米饭情有独钟。
Input
第一行，三个整数 N ，M ，K ，如题意所描述
第二行，两个整数 S ，T ，代表出发城市和目标城市编号
接下来 M 行，每行三个整数 X ，Y ，W ，代表 X 和 Y 城市之间的高速公路收费为 W 元
Output
共一行 ，输出一个整数 ，代表PCY 最少需要花费的路费。
*/
//看来我只有认真的阅读啦！！！！！
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define rg register
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int MAXN=5000010;
const int INF=0x3f3f3f3f;
struct node
{
int next;
int to;
int w;
} t[MAXN];
struct Heap
{
int a[MAXN],dist[MAXN];
int tail;
void clear()
{
tail=0;
}
void Swap(int x,int y)
{
swap( a[ x ],a[ y ] );
swap( dist[ x ],dist[ y ] );
}
void insert(rg int id,rg int d)
{
a[ ++tail ]=id,dist[ tail ]=d;
int tmp=tail;
while( tmp>=2 )
{
if( dist[ tmp ]<dist[ tmp/2 ] )
{
Swap( tmp,tmp/2 );
tmp=tmp/2;
}
else break ;
}
}
void update(rg int k)//??????????????
{
int tmp=k;
if( ls<=tail && dist[ ls ]<=dist[ tmp ] ) tmp=ls;
if( rs<=tail && dist[ rs ]<=dist[ tmp ] ) tmp=rs;
if( tmp!=k )
{
Swap( k,tmp );
update( tmp );
}
}
int top( )
{
return a[ 1 ];
}
void pop( )
{
a[ 1 ]=a[ tail ],dist[ 1 ]=dist[ tail-- ];
if( tail<=1 ) return ;
update( 1 );
}
int empty( )
{
return tail;
}
} q;//哥们儿有必要自己写priority_queue吗？
bool vis[MAXN];
int head[MAXN],num;
int dis[MAXN];
int n,m,k;
int S,T,ans=INF;
inline int gi()//快读
{
int x=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y,int z)
{
t[ ++num ].next=head[ x ];
t[ num ].to=y;
t[ num ].w=z;
head[ x ]=num;
}
inline void dijkstra( )
{
int x;
memset( dis,INF,sizeof dis);
q.clear();
dis[ S ]=0;
q.insert( S,0 );
while( q.empty() )
{
x=q.top(),q.pop();
if( vis[ x ] ) continue ;
vis[ x ]=1;
for(rg int i=head[ x ],y; i ;i=t[ i ].next )
{
y=t[ i ].to;
if( dis[ y ]>dis[ x ]+t[ i ].w && !vis[ y ] )
{
dis[ y ]=dis[ x ]+t[ i ].w;
q.insert( y,dis[ y ] );
}
}
}
}
int main()
{
int x,y,z,t0,t1,t2;
n=gi(),m=gi(),k=gi(),S=gi(),T=gi();//k是免费次数 ，n个城市
for(int i=1; i<=m; i++)
{
x=gi(),y=gi(),z=gi();
for(int j=0;j<=k;j++)
{
add( x+n*j,y+n*j,z ),add( y+n*j,x+n*j,z );//往图中加点
if( j<k ) add( x+n*j,y+n*(j+1),0 ),add( y+n*j,x+n*(j+1),0 );//和下一层图进行连接点的操作
}
}
dijkstra();
for(int i=0; i<=k; i++) ans=min( ans,dis[ T+i*n ] );
printf("%dn",ans);
return 0;
}
按照今天上午的安排（2018.2.27），今天下午本人A了一道分层图的题目：
题目链接：
2763: [JLOI2011]飞行路线（BZOJ）
下面为AC代码：
/**************************************************************
Problem: 2763
User: Mudrobot
Language: C++
Result: Accepted
Time:1144 ms
Memory:28768 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=200005;
int dis[maxn];
bool vis[maxn];
struct sd{
int len,num;
bool operator < (const sd &x) const
{
if(x.len<len)
{
return true;
}
return false;
}
}lin;
vector<sd> edge[maxn];
priority_queue<sd> q;
int n,m,k;
int s,e;
void add(int,int,int);
void Dijsktra();
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&e);//have zero city!!!!
int a,b,c;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=0;j<=k;++j)
{
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
if(j<k) {add(a+j*n,b+(j+1)*n,0);add(b+j*n,a+(j+1)*n,0);}
}
}
Dijsktra();
int ans=0x7f7f7f7f7f;
for(int i=0;i<=k;++i)
{
//cout<<dis[n*i+e]<<endl;
ans=min(ans,dis[n*i+e]);
}
printf("%d",ans);
return 0;
}
void Dijsktra()
{
memset(vis,false,sizeof(vis));
memset(dis,0x7f7f7f7f7f,sizeof(dis));
dis[s]=0;
sd ti;
ti.num=s;
ti.len=0;
q.push(ti);
while(!q.empty())
{
sd now;
now=q.top(); q.pop();
if(!vis[now.num])
{
vis[now.num]=true;
for(int i=edge[now.num].size()-1;i>=0;--i)
{
if(dis[edge[now.num][i].num]>dis[now.num]+edge[now.num][i].len)
{
dis[edge[now.num][i].num]=dis[now.num]+edge[now.num][i].len;
sd p;
p.num=edge[now.num][i].num;
p.len=dis[edge[now.num][i].num];
q.push(p);
}
}
}
}
}
void add(int aa,int bb,int cc)
{
lin.len=cc;
lin.num=bb;
edge[aa].push_back(lin);
}
/*
4 6 0
1 3
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
*/
只要你能够完全掌握Dijsktra priority的算法，这道题对于你来说就是一个非常简单的事情！唯一与Dijsktra priority不同的是多了一个add函数，他是用来建造分层图的。我们下面就来讲解一下add函数
add函数
代码：
void add(int aa,int bb,int cc)
{
lin.len=cc;
lin.num=bb;
edge[aa].push_back(lin);
}
这里主要用于建造高层的图，首先，我们可以很容易判断出图的层数取决于，能免费坐飞机的次数，而连接这些图之间就是权值为0的线段，而权值为0的线段连接的是在同一层中通过有权线段相连的点（但是在相邻不同的图中同一点位）【小括号部分做前面“点”的定语】
介于上面加黑的部分太不好理解，我们在这里举一个例子：
如果在同一个图中A,B相连，我们保证数据可以造出与此题相邻的图并且规定A，B在另一层图上为A'，B'。那么根据上面的规则，因为存在免费坐飞机的机会，所以A→B'之间会用一个权值为0的线段连接，同理，B→A'之间会用一个权值为0的线段连接。
所以相信大家应该都懂了吧！
那么我们在简述一下如何实现创造高层图的方法吧！
此部分代码：
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=0;j<=k;++j)
{
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
if(j<k) {add(a+j*n,b+(j+1)*n,0);add(b+j*n,a+(j+1)*n,0);}
}
}
注意：我们有k次免费坐飞机的机会，那么就有k+1个图
我们只要保证我们每一次创建的图满足
i*n+a（当前位置的标号）
n是指此图中有多少个点，大家脑补一下，其实这个也不难理解啦！
谢谢采纳！后续持续更新······
原文链接: https://www.cnblogs.com/mudrobot/p/13328861.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367885
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
