在 #152 RE → SubTask5 RE0pts
#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
ull n, m, k, s, t, LOG;
struct Node
{
ull to, w;
};
vector<bool> vis;
vector<ull> dis;
vector<vector<Node>> edg;
void dijkstra(ull x)
{
priority_queue<pair<ull, ull>, vector<pair<ull, ull>>, greater<pair<ull, ull>>> q;
dis.assign((LOG + 1) * n + 1024ull, 0x7f7f7f7f7f7f7full);
dis[x] = 0ull;
q.push({0ull, x});
while (!q.empty())
{
auto hd = q.top();
q.pop();
if (vis[hd.second])
continue;
vis[hd.second] = true;
for (auto targ : edg[hd.second])
{
if (dis[targ.to] > dis[hd.second] + targ.w)
{
dis[targ.to] = dis[hd.second] + targ.w;
q.push({dis[targ.to], targ.to});
}
}
}
}
int32_t main()
{
#ifdef ONLINE_JUDGE
freopen("sum.in", "r", stdin);
freopen("sum.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> k;
if (k > 1)
LOG = ceil(log10((ull)(1e9)) / log10(k));
else
LOG = 16ull;
edg.resize((LOG + 1ull) * n + 1024ull);
vis.resize((LOG + 1ull) * n + 1024ull, false);
dis.resize((LOG + 1ull) * n + 1024ull, 0x7f7f7f7f7f7f7full);
bool sp = false;
if (k == 1ull)
sp = true;
for (ull i = 1ull; i <= m; i++)
{
ull u, v, w;
cin >> u >> v >> w;
edg[u].push_back({v, sp ? 1ull : w});
edg[v].push_back({u, sp ? 1ull : w});
ull cnt = 1;
for (ull j = 1; j <= LOG; j++)
{
edg[u + (j - 1ull) * n].push_back({v + j * n, cnt});
edg[v + (j - 1ull) * n].push_back({u + j * n, cnt});
edg[u + j * n].push_back({v + j * n, sp ? 1ull : w});
edg[v + j * n].push_back({u + j * n, sp ? 1ull : w});
cnt *= k;
if (cnt > (ull)(1e9))
break;
}
}
cin >> s >> t;
dijkstra(s);
ull ans = 0x7f7f7f7f7f7f7full;
for (ull i = 0ull; i <= LOG; i++)
ans = min<ull>(ans, dis[t + i * n]);
cout << ans << endl;
return 0;
}