飞行路线 改造路 分层最短路【模板】

P4568 P2939 >给你一张带权图,你可以用不大于K次机会免费通过一条边(或者是以其他费用通过),问你从起点到终点最短路径花费。

分层最短路就是用来处理这一问题的,其实就是变了点形的Dp,只是名字高级了一点,貌似也只能处理这一问题了。无非就是设,其意就是到达点用了次机会所用的最小花费。

而分层最短路大概就是把图扩充为好几层,每一层代表的含义就是使用了几次机会。如果到了下一层那么就是免费(或其他),在这一层里走就是正常花费。其实还是挺好理解的(Ps:只是把二维的Dp变成了一维)。

而且代码只是在最短路的代码上多连了几条边,一般都是用堆优化的跑,因为给你的点数一般为10000,而且边不算稀,用SPFA较慢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
struct Mystruct{
int ne,to,w;
}edge[4105050];
int n,m,k,head[212020],tail,dis[212020];
bool v[212020];
#define add(x,y,z) edge[++tail].ne=head[x];edge[tail].to=y;edge[tail].w=z;head[x]=tail;
void dij(){
priority_queue<pair<int,int> >q;
//用优先队列码量小,跟堆的作用一样
//pair为二元组,把俩者绑在一起,默认的是先从第一个比较大小,若相等则比较第二个
//此时这里默认的是大根堆,此时可以自定义比较,或者把dis把它变成负的就ok了
//也可以这样 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q
//又长又臭, 倾向于第一种
q.push(make_pair(0,1));//就当起点是1,终点是N了
while(!q.empty()){
int x=q.top().second;
//pair以 .first 访问第一个,以 .second 访问第二个
q.pop();
if(v[x])continue;
v[x]=1;
for(int i=head[x];i;i=edge[i].ne){
int diss=dis[x]+edge[i].w;
if(dis[edge[i].to]>=diss){
dis[edge[i].to]=diss;
q.push(make_pair(-diss,edge[i].to));
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1,x,y,z;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
//第0层互相连边
for(int j=1;j<=k;++j){
//1 - n 为第0层,1+n - n+n 为第1层 ……
add(x+(j-1)*n,y+j*n,0);
add(y+(j-1)*n,x+j*n,0);
//第j-1层与第j层连边
add(y+j*n,x+j*n,z);
add(x+j*n,y+j*n,z);
//第j层互相连边
}
}
//初始化
for(int i=1;i<=n*(k+1);++i)
dis[i]=0x7fffffff;
dis[1]=0;
dij();
int ans=0x7fffffff;
//别忘了可能还没用够K次机会就到终点了
for(int i=n;i<=n*(k+1);i+=n)
ans=min(ans,dis[i]);
printf("%d",ans);
}

飞行路线 改造路 分层最短路【模板】

http://www.therehello.top/fen-ceng-zui-duan-lu/

发布于

2019-10-14

更新于

2021-10-24

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...