大家好!我是老码农。
这次期末考试游说的还不错,小码匠没有每天复习,上周日一大早我就甩给她一道分层图的题目。
给她找了个有关分层图讲解的视频,她看了一会,哦,会了。
话说B站上的视频,太千篇一律了,都是同一道题,只是不同人讲解罢了,就不用有一点心意吗?
在说分层图的模版题又不止那一道,为啥非得都选那道题啊。
吐槽归吐槽,题还是要刷的。
小码匠刷的还算顺利,一会搞完了。
直接提交,华丽丽的挂了,91分,一个点RE了。
弄的小码匠很郁闷啊。
东试西试,后来把空间开大了,直接提交AC了。
我问她:搞明白为啥开这么大了吗?
她一脸懵,没想明白,反正就是过了。
一知半解的状态是最可怕的,虽然看似题做出来了,但没完全弄明白,下次遇到估计还会跌倒。
之后我又给她找了一道分层图题,我就出去了,回来听匠她娘说,你刚出去一会,我看她就AC了,
题目太水了吧。
晚上我又想起白天的事,就问小码匠:早晨那道题搞明白为啥空间开那么大了吗?
原本我以为她没想明白,想让她去去评论区发个帖子问问。
她娓娓道来,口若悬河一通说,反正我是没怎么听明白了。
重点:她搞明白就行了。
贴上AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 1e4;
int n, m, k, s, t;
bool vis[maxn];
ll dis[maxn];
struct edge {
ll w;
int to;
};
bool operator< (const edge& a, const edge& b) {
return a.w > b.w;
}
vector<edge> g[maxn];
void dijkstra () {
priority_queue<edge> q;
memset(dis, 0x7f, sizeof(dis));
q.push({0ll, s});
dis[s] = 0;
while (!q.empty()) {
auto u = q.top();
q.pop();
if (vis[u.to]) {
continue;
}
vis[u.to] = true;
for (auto v : g[u.to]) {
if (dis[v.to] > dis[u.to] + v.w) {
dis[v.to] = dis[u.to] + v.w;
v.w = dis[v.to];
q.push(v);
}
}
}
}
void best_coder() {
cin >> n >> m >> k >> s >> t;
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
g[u].push_back({w, v});
g[v].push_back({w, u});
for (int j = 1; j <= k; ++j) {
g[j * n + u].push_back({w, j * n + v});
g[j * n + v].push_back({w, j * n + u});
g[(j - 1) * n + u].push_back({0, j * n + v});
g[(j - 1) * n + v].push_back({0, j * n + u});
}
}
dijkstra();
ll ans = LONG_LONG_MAX;
for (int i = 0; i <= k; ++i) {
ans = min(ans, dis[i * n + t]);
}
cout << ans;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}