武理校赛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 分钟才在推优的提醒下发现算法写假。
另一原因也是以前没有写过分层图的题目，所以比赛时即便想到可能可以建三层图，却无法确定是否可行，在两种思路中果断选择了错误的思路 （不愧是我）