本文主要是介绍武理校赛D题 星际穿越(分层图 + dij堆优化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
武理校赛D题
星际穿越(分层图 + dij堆优化)
牛客链接
题意:
给定 N 个点,M 条边,每条边有边权 w,点分为三类,编号为1,2,3。
给定起点和终点且保证起点和终点都是第 3 类点。
求起点到终点的最短路,且路径中需要有一个 (不多不少刚好一个)1 类点和一个 2 类点,通过 1 类点的时间要在通过 2 类点之前。
保证数据无重边,无负环,图连通。
思路:
第一眼看过去类似一个最短路问题,只不过加了限制条件,因此考虑使用最短路解决。
典中典之错误思路:
一开始想到将所有 1 类点都连接一个边权为 0 的超级源点,2 类点同理,这样可以将模型大概简化为:所有三类点 -> 所有一类点 -> 所有二类点 -> 所有三类点,跑三次 dij 找到答案。
(最后发现这种算法假了qwq)
这种建图无法保证:
局部最优解是全局最优解;
存在 三类点 -> 二类点 -> 一类点 的可能;
正确思路:
建分层图,分三层:
每一层中的三类点都是联通的;
第一层路径包括 3 -> 3,3 -> 1;
从第一层到第二层的路径由 1 -> (第二层的)3 组成;
第二层路径包括 3 -> 3,1 -> 3;
第二层到第三层的路径由 1 -> (第三层的)2,3 -> (第三层的)2 组成;
第三层路径包括 3 -> 3,2 -> 3;
建完图之后只要从第一层的起点跑到第三层的终点,跑一边 dij 即可算出答案。
细节:
三层图,因此 MAXN 和 MAXM 都要开成三倍;
距离初始化时也要初始化到 3 * n;
const int MAXN = 300010;
const int MAXM = 1500010;
for (int i = 1;i <= n * 3 + 2;i++) dis[i] = inf;
剩下没啥细节基本都是模板
完整代码:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<int, int> pii;
typedef pair<dd, dd> pdd;
const int MAXN = 300010;
const int inf = 1e9 + 7;
const int MAXM = 1500010;//dij 模板
struct EDGE {int u, v, w, nxt;
}e[MAXM];
int head[MAXN], cnt, vis[MAXN], dis[MAXN];
struct NODE {int w, now;bool operator < (const NODE& x) const{return w > x.w;}
};
priority_queue<NODE>q;
int n, m, s, t;
int lei[MAXN];void add(int u, int v, int w)
{e[++cnt] = { u,v,w,head[u] };head[u] = cnt;
}void dij()
{for (int i = 1;i <= n * 3 + 2;i++) dis[i] = inf;dis[s] = 0;q.push({ 0,s });while (q.size()){NODE x = q.top();q.pop();int u = x.now;if (vis[u]) continue;vis[u] = 1;for (int i = head[u];i;i = e[i].nxt){int v = e[i].v;if (dis[v] > dis[u] + e[i].w){dis[v] = dis[u] + e[i].w;q.push({ dis[v],v });}}}
}int main()
{scanf("%d%d%d%d", &n, &m, &s, &t);for (int i = 1;i <= n;i++) scanf("%d", &lei[i]);for (int i = 1;i <= m;i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);if (lei[u] == 3 && lei[v] == 3) add(u, v, w), add(u + n, v + n, w), add(u + 2 * n, v + 2 * n, w);//3 -> 3, 每层都建if (lei[u] == 3 && lei[v] == 1) add(u, v + n, w);//3 -> 1, 第一层到第二层的路径if (lei[u] == 3 && lei[v] == 2) add(u + n, v + 2 * n, w);//3 -> 2, 第二层到第三层的路径if (lei[u] == 1 && lei[v] == 2) add(u + n, v + 2 * n, w);//1 -> 2, 第二层到第三层的路径if (lei[u] == 1 && lei[v] == 3) add(u + n, v + n, w);//1 -> 3, 第二层中的路径if (lei[u] == 2 && lei[v] == 3) add(u + 2 * n, v + 2 * n, w);//2 -> 3, 第三层中的路径}dij();if (dis[t + 2 * n] >= inf) printf("-1");//第一层起点到第三层终点的最短路径else printf("%d", dis[t + 2 * n]);
}
总结:
比赛写这题时心态较急,导致没有仔细思考当时的思路是否可行就开始写,导致一直按照错误思路写到最后 20 分钟才在推优的提醒下发现算法写假。
另一原因也是以前没有写过分层图的题目,所以比赛时即便想到可能可以建三层图,却无法确定是否可行,在两种思路中果断选择了错误的思路 (不愧是我)
这篇关于武理校赛D题 星际穿越(分层图 + dij堆优化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!