P4568[JLOI2011]飞行路线考虑跑多层图，每层图连条边权为0的边，跑dijkstra即可。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e7+10;intn,m,k,s,t;intcnt;inthead[N];structss{ intto,w,next;}a[N];voidadd(intu,int

题目P4568[JLOI2011]飞行路线要求找到在最多可以免费乘坐k条航线的情况下，从城市s到城市t的最少花费。这是一个典型的分层图问题。分层图的建模1.建立层次将原图分成k+1层，表示在0到k次免费乘坐的情况下的状态。第i层表示已经使用了i次免费乘坐机会的状态。2.建立节点和边