当前位置：首页 > article >正文

分层图最短路

article 2024/12/5 3:23:58

常见情形：

对于边有k次操作的题。。

整体思想：

分层图最短路可以视作是dijkstra的一个扩展，通常用于处理N小于10000，或者是k不大的情形。整体有点类似于拆点。将一个点拆成k个点处理。层与层之间互不影响。

好了我就说这么多，剩下来的交给想象力，这个自己相通了就不难理解。

经典例题：

一：3095. 冻结

“我要成为魔法少女！”

“那么，以灵魂为代价，你希望得到什么？”

“我要将有关魔法和奇迹的一切，封印于卡片之中......”

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

现在，不需要立下契约也可以使用魔法了！

你还不来试一试？

比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。

例如，我们熟知的 Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。

当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。

这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi......

当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。

我们考虑最简单的旅行问题吧：

现在这个大陆上有 NN 个城市，MM 条双向的道路。

城市编号为 1∼N1∼N，我们在 11 号城市，需要到 NN 号城市，怎样才能最快地到达呢？

这不就是最短路问题吗？

我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。

现在，我们一共有 KK 张可以使时间变慢 50%50% 的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间就可以减少到原先的一半。

需要注意的是：

在一条道路上最多只能使用一张 SpellCard。
使用一张 SpellCard 只在一条道路上起作用。
你不必使用完所有的 SpellCard。

给定以上的信息，你的任务是：

求出在可以使用这不超过 KK 张时间减速的 SpellCard 之情形下，从城市 11 到城市 NN 最少需要多长时间。

输入格式

第一行包含三个整数：N、M、KN、M、K。

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

输出格式

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

数据范围

1≤K≤N≤501≤K≤N≤50,
1≤M≤10001≤M≤1000,
1≤Ai,Bi≤N1≤Ai,Bi≤N,
2≤Timei≤20002≤Timei≤2000,
为保证答案为整数，保证所有的 TimeiTimei 均为偶数。
所有数据中的无向图保证无自环、重边，且是连通的。

输入样例：
4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
输出样例：
7
样例解释

在不使用 SpellCard 时，最短路为 1→2→41→2→4，总时间为 1010。

现在我们可以使用 11 次 SpellCard，那么我们将通过 2→42→4 这条道路的时间减半，此时总时间为 77。
#include<bits/stdc++.h>
using namespace std;
const int N=60,M=2010;
typedef pair<int,pair<int,int>>PII;
int h[N],e[M],ne[M],w[M],idx;
int dis[N][N];
bool st[N][N];
int n,m,k;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dij()
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,{1,0}});
    dis[1][0]=0;
    while(q.size()){
        auto t=q.top();
        q.pop();
        int v=t.second.first;
        int u=t.second.second;
        if(st[v][u]){
            continue;
        }
        st[v][u]=true;
        for(int i=h[v];~i;i=ne[i]){
            int j=e[i];
            if(st[j][u]){
                continue;
            }
            if(u+1<=k){
                if(dis[j][u+1]>dis[v][u]+w[i]/2){
                    dis[j][u+1]=dis[v][u]+w[i]/2;
                    q.push({dis[j][u+1],{j,u+1}});
                }
            }
            if(dis[j][u]>dis[v][u]+w[i]){
                dis[j][u]=dis[v][u]+w[i];
                q.push({dis[j][u],{j,u}});
            }
        }
    }
}
void solve()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dij();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++){
        //cout<<dis[n][i]<<endl;
        ans=min(dis[n][i],ans);
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

二：340. 通信线路

在郊区有 NN 座通信基站，PP 条双向电缆，第 ii 条电缆连接基站 AiAi 和 BiBi。

特别地，11 号基站是通信公司的总站，NN 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 ii 条电缆需要花费 LiLi。

电话公司正在举行优惠活动。

农产主可以指定一条从 11 号基站到 NN 号基站的路径，并指定路径上不超过 KK 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 11 行：三个整数 N，P，KN，P，K。

第 2..P+12..P+1 行：第 i+1i+1 行包含三个整数 Ai,Bi,LiAi,Bi,Li。

输出格式

包含一个整数表示最少花费。

若 11 号基站与 NN 号基站之间不存在路径，则输出 −1−1。

数据范围

0≤K<N≤10000≤K<N≤1000,
1≤P≤100001≤P≤10000,
1≤Li≤10000001≤Li≤1000000

输入样例：
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样例：
4
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, pair<int, int>>PII;
const int N = 1010,M=20010;
int h[N], e[M], ne[M], w[M], idx;
int dis[N][N];
bool st[N][N];
int n, m, k;
int ans=0x3f3f3f3f;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dij()
{
	memset(dis, 0x3f, sizeof dis);
	priority_queue<PII, vector<PII>, greater<PII>>q;
	q.push({ 0,{1,0} });
	dis[1][0] = 0;
	while (q.size()) {
		auto t = q.top();
		q.pop();
		int v = t.second.first;
		int u = t.second.second;
		if (st[v][u]) {
			continue;
		}
		st[v][u] = true;
		for (int i = h[v];~i;i = ne[i]) {
			int j = e[i];
			if (st[j][u]) {
				continue;
			}
			if (u + 1 <= k) {
				if (dis[j][u + 1] > dis[v][u] ) {
					dis[j][u + 1] = dis[v][u] ;
					q.push({ dis[j][u + 1],{j,u + 1} });
				}
			}
			if (dis[j][u] > max(dis[v][u] , w[i])) {
				dis[j][u] =max( dis[v][u] , w[i]);
				q.push({ dis[j][u], { j,u } });
			}
		}
	}
}
void solve()
{
	cin >> n >> m >> k;
	memset(h, -1, sizeof h);
	for (int i = 1;i <= m;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dij();
	for (int i = 0;i <= k;i++) {
		//cout << dis[n][i] << endl;
		ans = min(ans, dis[n][i]);
	}
	if (ans == 0x3f3f3f3f) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	solve();
	return 0;
}