P4568 [JLOI2011]飞行路线

思路

套路题

建出k+1分层图,从上一层走到下一层代表坐了一次免费航线,跑最短路即可

注意可能有情况不需要耗完所有k次机会,所以应从每层的终点向下一层终点连一条边权为0的边

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int u[4000100],v[4000100],w[4000100],fir[4000100],nxt[4000100],cnt,n,m,k,s,t,dis[4000100],vis[4000100];
struct QNode{
int dis,x;
bool operator < (const QNode &b) const{
return dis>b.dis;
}
};
priority_queue<QNode> q;
void addedge(int ui,int vi,int wi){
++cnt;
u[cnt]=ui;
v[cnt]=vi;
w[cnt]=wi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
void dij(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push((QNode){0,s});
while(!q.empty()){
QNode u=q.top();
q.pop();
if(vis[u.x])
continue;
vis[u.x]=true;
for(int i=fir[u.x];i;i=nxt[i]){
if(dis[v[i]]>dis[u.x]+w[i]){
dis[v[i]]=dis[u.x]+w[i];
q.push((QNode){dis[v[i]],v[i]});
}
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
scanf("%d %d",&s,&t);
s++;
t++;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
a++,b++;
for(int j=1;j<=k+1;j++){
addedge(a+(n*(j-1)),b+(n*(j-1)),c);
addedge(b+(n*(j-1)),a+(n*(j-1)),c);
}
for(int j=1;j<=k;j++){
addedge(a+(n*(j-1)),b+(n*(j)),0);
addedge(b+(n*(j-1)),a+(n*(j)),0);
}
}
for(int i=1;i<=k;i++)
addedge(t+(n*(i-1)),t+(n*i),0);
dij(s);
printf("%d\n",dis[t+k*n]);
return 0;
}
上一篇:linux下redis 集群配置


下一篇:AndroidStudio 快捷键 Ctrl+Q查询过慢的问题