bzoj 2763 [JLOI2011]飞行路线 Dijikstra 分层

xiaoxiao2021-02-28  25

k<=10，所以每用一次机会就跳到一个新图中，

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<iostream> #define N 500500 using namespace std; int n,m,k,S,T; struct point{ int st,dis; bool operator < (const point &a)const{ return dis>a.dis; } }p[N]; int e=1,head[N],dis[N]; bool bo[N]; struct edge{ int u,v,w,next; }ed[5000500]; void add(int u,int v,int w){ ed[e].u=u; ed[e].v=v; ed[e].w=w; ed[e].next=head[u]; head[u]=e++; } priority_queue<point> q; int dijkstra(){ memset(dis,0x7f,sizeof dis); memset(bo,0,sizeof bo); dis[S]=0;q.push((point){S,0}); while(!q.empty()){ point now=q.top();q.pop(); if(bo[now.st]) continue; bo[now.st]=1; for(int i=head[now.st];i;i=ed[i].next) if(dis[now.st]+ed[i].w<dis[ed[i].v]){ dis[ed[i].v]=dis[now.st]+ed[i].w; q.push((point){ed[i].v,dis[ed[i].v]}); } } int ans=0x7fffffff; for(int i=0;i<=k;i++) ans=min(ans,dis[i*n+T]); return ans; } int main(){ scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&S,&T);S++;T++; int u,v,w; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); u++;v++; for(int j=0;j<=k;j++){ add(j*n+u,j*n+v,w),add(j*n+v,j*n+u,w); if(j<k)add(j*n+u,(j+1)*n+v,0),add(j*n+v,(j+1)*n+u,0); } } int ans=dijkstra(); printf("%d\n",ans); return 0; }