分层图最短路

发表于
字数统计: 2,449 | 阅读时长 ≈ 11

前言

随便写写
尽量保持日更…（我觉得做不到

分层图最短路

我们在解决单源最短路的时候，在学习了像spfa这样的算法之后，会变的很简单
那么如果我们遇到像可以将k条边的权值变成 0 ，再求最短路，这样我们只跑单源最短路径显然是不行的、
我们可以经过某些权值很大的边（本身不在单源最短路径上），把这条边的权值变为 0 ，那么整条路径上的最短路就变得很小
来看这样一张图

我们要求点 1 和点 3 的单源最短路
显然 1 —> 4 -> 5 -> 3 的路径权值和最小为 4+3+1=8
但是如果我们可以讲路径上一条边的权值变成 0 ，那么这种情况显然不是最短路了
我们可以看到 1 -> 2 -> 3 = 8+2，把 1 -> 2 这条边的权值变为 0 ，这时的单源最短路径的权值和为 2 ，最小
因此我们将如何处理这类问题呢？

我们考虑DP的思想 用 dp[i][j] 表示从起点跑到点 i 并且使用了 k 次改变后得到的最小距离，跑法也是 spfa 不过我们需要考虑一些别的东西

对于询问到下一个点，我们有两种选择，一种是不用变化，一种是用变换
我们先跑一次 spfa ，这一次我们不进行变换
我们在跑完这一次 for 循环之后再跑一次，这一次表示的是我们进行变换 dp[to[u]][k+1]=dp[u][k]; 转移方程很好想
本身这个东西随便讲一下就懂了的，所以以下有两道模板题，我们来看一下

BZOJ2763

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务，设这些城市分别标记为 0 到 n-1 ，一共有 m 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 k 种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

输入输出格式

输入格式：

数据的第一行有三个整数， n,m,k ，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数， s,t ，分别表示他们出行的起点城市编号和终点城市编号。
接下来有m行，每行三个整数， a,b,c ，表示存在一种航线，能从城市 a 到达城市 b ，或从城市 b 到达城市 a ，价格为 c 。

输出格式：

只有一行，包含一个整数，为最少花费。

输入输出样例

输入样例#1：
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
输出样例#1：
8

说明

2 <= n <=10000,1 < m <= 50000,0 <= k <= 10,c <= 1000

解题思路

解释分层图很清晰了…
反正也是模板题直接上代码好了

AC代码212ms

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// luogu-judger-enable-o2
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<utility> 
#include<functional>

int Read(){
    int x=0;char c=getchar();
    while(!isdigit(c)){
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

using std::priority_queue;
using std::pair;
using std::vector;
using std::make_pair;
using std::greater;

struct Edge{
    int to,next,cost;
}edge[2500001];
int cnt,head[110005];

void add_edge(int u,int v,int c=0){
    edge[++cnt]=(Edge){v,head[u],c};
    head[u]=cnt;
}

int dis[110005];
bool vis[110005];
void Dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > points;
    points.push(make_pair(0,s));
    while(!points.empty()){
        int u=points.top().second;
        points.pop();
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next){
                int to=edge[i].to;
                if(dis[to]>dis[u]+edge[i].cost) {
                    dis[to]=dis[u]+edge[i].cost;
                    points.push(make_pair(dis[to],to));
                }
            }
        }
    }
}

int main(){
    int n=Read(),m=Read(),k=Read(),s=Read(),t=Read();
    int u,v,c;
    for(int i=0;i<m;++i){
        u=Read(),v=Read(),c=Read();
        add_edge(u,v,c);
        add_edge(v,u,c);
        for(int j=1;j<=k;++j){
            add_edge(u+(j-1)*n,v+j*n);
            add_edge(v+(j-1)*n,u+j*n);
            add_edge(u+j*n,v+j*n,c);
            add_edge(v+j*n,u+j*n,c);
        }
    }
    for(int i=1;i<=k;++i){
        add_edge(t+(i-1)*n,t+i*n);
    }
    Dijkstra(s);
    printf("%d",dis[t+k*n]);
    return 0;
}

BZOJ2662

Description

“我要成为魔法少女！”
“那么，以灵魂为代价，你希望得到什么？”
“我要将有关魔法和奇迹的一切，封印于卡片之中„„”

在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符
卡）带来的便捷。

现在，不需要立下契约也可以使用魔法了！你还不来试一试？
比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关
键字来查询，会有很多有趣的结果。
例如，我们熟知的Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。 当然，
更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小
巫见大巫了。
这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、„„
当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。

我们考虑最简单的旅行问题吧： 现在这个大陆上有 N 个城市，M 条双向的道路。城市编号为 1~N，我们在 1 号城市，需要到 N 号城市，怎样才能最快地到达呢？
这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。
现在，我们一共有 K 张可以使时间变慢 50%的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是：

  1. 在一条道路上最多只能使用一张 SpellCard。
  2. 使用一张SpellCard 只在一条道路上起作用。

  3. 你不必使用完所有的 SpellCard。

    给定以上的信息，你的任务是：求出在可以使用这不超过 K 张时间减速的SpellCard 之情形下，从城市1 到城市N最少需要多长时间。

Input

第一行包含三个整数：N、M、K。
接下来 M 行，每行包含三个整数：Ai、Bi、Timei，表示存在一条 Ai与 Bi之
间的双向道路，在不使用 SpellCard 之前提下，通过它需要 Timei的时间。

Output

输出一个整数，表示从1 号城市到 N号城市的最小用时。

Sample Input

4 4 1 
1 2 4 
4 2 6 
1 3 8 
3 4 8

Sample Output

7

【样例1 解释】

在不使用 SpellCard 时，最短路为 1à2à4，总时间为 10。现在我们可
以使用 1 次 SpellCard，那么我们将通过 2à4 这条道路的时间减半，此时总
时间为7。

HINT

对于100%的数据：1 ≤ K ≤ N ≤ 50，M ≤ 1000。

1≤ Ai，Bi ≤ N，2 ≤ Timei ≤ 2000。

为保证答案为整数，保证所有的 Timei均为偶数。

所有数据中的无向图保证无自环、重边，且是连通的。

解题思路

只是有两道很相似的题
跟上题类似只是把权值赋为一半
连边情况接近模板

AC代码

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
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<algorithm>
#define re register int
#define xep(i,x) for(re i=head[x];i;i=nxt[i])
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=1010;
int n,m,k,cnt=0;
int dis[N][N],vis[N][N];
int head[N],nxt[N<<1],to[N<<1],val[N<<1];
struct node{
	int num,type;
	node(int x,int y):num(x),type(y){}
	node(){}
};
queue < node > q;

inline void add(int x,int y,int v){
	to[++cnt]=y;nxt[cnt]=head[x];
	head[x]=cnt;val[cnt]=v;
}

inline void spfa(){
	memset(dis,inf,sizeof(dis));
	q.push(node(1,0));dis[1][0]=0;vis[1][0]=1;
	while(!q.empty()){
		node u=q.front();q.pop();
		xep(i,u.num){
			int v=to[i];
			if(dis[v][u.type]>dis[u.num][u.type]+val[i]){
				dis[v][u.type]=dis[u.num][u.type]+val[i];
				if(!vis[v][u.type]) 
					q.push(node(v,u.type)),vis[v][u.type]=1;
			}
			if(u.type<k){
				if(dis[v][u.type+1]>dis[u.num][u.type]+(val[i]>>1)){
					dis[v][u.type+1]=dis[u.num][u.type]+(val[i]>>1);
					if(!vis[v][u.type+1])
						vis[v][u.type+1]=1,q.push(node(v,u.type+1));
				}
			}
		}
	}
	int ans=inf;
	for(re i=1;i<=k;i++) ans=min(ans,dis[n][i]);
	printf("%d",ans);
}

int main(){
	n=read();m=read();k=read();
	for(re i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		add(x,y,z);add(y,x,z);
	}
	spfa();
	return 0;
}

后记

本身就是随便写一下博客
这类题目第一次看到会有点无所适从
但是知道怎么解了就会异常简单（spfa也很好打啊
所以我们来看一下我们联系方式…

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan

欢迎指正…