P4568 [JLOI2011]飞行路线
分层图模板题，相似的题还有P4822 [BJWC2012]冻结，
P2939 [USACO09FEB]改造路Revamping Trails,其实做惯了也就不难了。。
为什么有这篇题解？
-
感觉写的比较简洁清晰 -
线段树优化最短路
一、堆优化dijkstra
652ms / 25.58MB / 1.31KB C++
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=110005,MAXM=2500001;
struct edge {
int to,dis,next;
} e[MAXM];
int n,m,k,s,t,head[MAXN],dis[MAXN],cnt;
bool vis[MAXN];
struct node {
int dis,pos;
bool operator <(const node &x)const {
return x.dis<dis;
}
};
priority_queue<node> q;
inline void add_edge(int u,int v,int d) {
e[++cnt].dis=d;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void dijkstra() {
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push((node) {
0,s
});
while(!q.empty()) {
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if (vis[x]) continue;
vis[x]=1;
for (int i=head[x]; i; i=e[i].next) {
int y=e[i].to;
if (dis[y]>dis[x]+e[i].dis) {
dis[y]=dis[x]+e[i].dis;
if (!vis[y])
q.push((node) {
dis[y],y
});
}
}
}
}
int main() {
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
for (register int i=0; i<m; i++) {
register int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v,d),add_edge(v,u,d);
for(int j=1; j<=k; ++j) {
add_edge(u+(j-1)*n,v+j*n,0);
add_edge(v+(j-1)*n,u+j*n,0);
add_edge(u+j*n,v+j*n,d);
add_edge(v+j*n,u+j*n,d);
}//每层之间建边
}
for(int i=1; i<=k; ++i) {
add_edge(t+(i-1)*n,t+i*n,0);//每层终点连边（不一定用K次最优）
}
dijkstra();
printf("%d",dis[k*n+t]);
return 0;
}
二、线段树dijkstra
523ms / 26.64MB / 1.41KB C++
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110005,M=2500001;
int n,m,kth,cnt,s,t;
int tr[N<<2],h[N],nxt[M],to[M],w[M],dis[N];
#define R register int
inline int rd() {
int t=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
return t;
}
inline void add_edge(int u,int v,int _w) {
nxt[++cnt]=h[u],to[cnt]=v,w[cnt]=_w,h[u]=cnt;
}
#define min(a,b) (dis[a]<dis[b]? a:b)
inline void modify(int o,int l,int r,int pos,int val) {
if (l==r) {
tr[o]=val;
return;
}
int mid=l+r>>1;
if (pos<=mid) modify(o<<1,l,mid,pos,val);
else modify(o<<1|1,mid+1,r,pos,val);
tr[o]=min(tr[o<<1],tr[o<<1|1]);
}
inline void dijkstra() {
memset(dis,0x3f,sizeof(dis));
dis[s]=0,modify(1,1,kth*n,s,s);//线段树存点的编号，然后通过比较dis上传
for (R t=1,u,v; t<kth*n; t++) {
u=tr[1],modify(1,1,kth*n,u,0);//dis0始终保持0x3f，作为删除操作
for (R i=h[u]; i; i=nxt[i])
if (dis[v=to[i]]>dis[u]+w[i])
dis[v]=dis[u]+w[i],modify(1,1,kth*n,v,v);
}
}
int main() {
n=rd(),m=rd(),kth=rd(),s=rd()+1,t=rd()+1;//编号加1，空出dis0的位置
for (R i=1,u,v,_w; i<=m; i++) {
u=rd()+1,v=rd()+1,_w=rd();
add_edge(u,v,_w),add_edge(v,u,_w);
for(int j=1; j<=kth; ++j) {
add_edge(u+(j-1)*n,v+j*n,0);
add_edge(v+(j-1)*n,u+j*n,0);
add_edge(u+j*n,v+j*n,_w);
add_edge(v+j*n,u+j*n,_w);
}
}
for (R i=1;i<=kth;i++)
add_edge(t+(i-1)*n,t+i*n,0);
kth++;
dijkstra();
printf("%d",dis[(kth-1)*n+t]);
return 0;
}
三、DP最短路
296ms / 2.26MB / 1.15KB C++
这种方法最快，而且数组的范围比较好确定
注意dis，vis，node是二维，要记录点的编号和所用次数
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct edge {
int v,w,h;
} e[100010];
int n,m,K,s,t,cnt,ans,h[10010],d[10010][11];
bool vis[10010][11];
struct node {
int u,k;
bool operator <(const node &x) const {
return d[u][k]>d[x.u][x.k];
}
};
inline void add(int u,int v,int w) {
e[++cnt]=(edge) {v,w,h[u]},h[u]=cnt;
}
inline void dijkstra() {
priority_queue<node> q;
memset(d,0x3f,sizeof d);
q.push((node) {
s,0
}),d[s][0]=0,vis[s][0]=1;//s点，用了0次
while(!q.empty()) {
node x=q.top();
q.pop(),vis[x.u][x.k]=0;
for (register int i=h[x.u],v,u,k; i; i=e[i].h) {
if (d[v=e[i].v][k=x.k]>d[u=x.u][k]+e[i].w) {
d[v][k]=d[u][k]+e[i].w;
if (!vis[v][k]) q.push((node) {
v,k
}),vis[v][k]=1;
}//更新不使用的情况，k不变
if (d[v][k+1]>d[u][k] && k<K) {
d[v][k+1]=d[u][k];
if (!vis[v][k+1] && k<K) q.push((node) {
v,k+1
}),vis[v][k+1]=1;
}//更新使用的情况，k加1且小于K
}
}
}
int main() {
scanf("%d%d%d%d%d",&n,&m,&K,&s,&t);
for (int i=1,u,v,w; i<=m; i++)
scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
dijkstra();
ans=1e9;
for (int i=0; i<=K; i++)
ans=ans<d[t][i]? ans:d[t][i];//用几次最优
printf("%d",ans);
}