KEYENCE Programming Contest 2023 Autumn(AtCoder Beginner Contest 325) - AtCoder E
E - Our clients, please wait a moment (atcoder.jp)(分层图最短路)
因为只能从坐公司汽车切换到做火车,所以我们可以考虑采用分层图最短路.
对于坐公司汽车和坐火车分别建立\(G_0\)和\(G_1\)两张图,且因为可以在任意时刻任意地点从公司汽车切换到火车,所以我们可以对于每个地点建立\(\forall x(G_0(x) \rightarrow G_1(x))\)的边权为\(0\)的有向边,\(G_0\)为第一层,有节点\(1 \sim n\),即公司汽车的路线;第二层有节点\(1+n \sim n + n\),即火车的路线,两层节点间\(i\)与\(i+n\)也用权值为0的有向边连起来,起点为第一层的\(1\),终点就是第二层的\(n+n\),注意因为分层,所以分层图\(dis\)范围初始化是\(K\)(\(K\)层)\(\times N + N\)(\(N\)个点).
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
const int MAXV = 1e4 + 1;
struct edge {
i64 to, cost;
};
vector<edge> G[MAXV];
i64 d[3010];
void dijkstra(int s) {
priority_queue<PII, vector<PII>, greater<PII> > que;
memset(d, 0x3f3f3f3f, sizeof d);
d[s] = 0;
que.push(PII(0, s));
while (!que.empty())
{
PII p = que.top(); que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); i++) {
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(PII(d[e.to], e.to));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int A, B, C, N;
cin >> N >> A >> B >> C;
vector D(N + 1, vector<i64>(N + 1));
for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j ++)
cin >> D[i][j];
for (int i = 1; i <= N; i ++) {
for (int j = 1; j <= N; j ++) {
if (i == j) continue;
G[i].push_back(edge{j, D[i][j] * A});
G[i].push_back(edge{i + N, 0});
G[i + N].push_back(edge{j + N, D[i][j] * B + C});
}
}
dijkstra(1);
cout << d[N + N] << '\n';
return 0;
}
参考资料
浅析分层图最短路 - feather02的博客 - 洛谷博客 (luogu.com.cn)
ABC325E 题解 - Welcome to CultReborn's Blog - 洛谷博客 (luogu.com.cn)
分层图复习 / abc325e - 可可爱爱 - 洛谷博客 (luogu.com.cn)
- Contest Programming Beginner KEYENCE AtCodercontest programming beginner keyence contest programming beginner atcoder programming keyence contest greedy programming keyence contest 2020 programming keyence contest 2019 contest programming securities beginner contest programming beginner registry contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295