挂飞了呜呜呜……100 挂成 10 了。。。
讲一下我的解法吧。
对于 k=1，明显只要一直用魔法就行了。直接可以看成边权为 1 的无向图，跑 bfs 就行了。
对于其他情况，我们可以先预处理出用魔法的边权。可以把边权存在一个数组里，我用 p_i 表示：已经使用过 i 次魔法时的边权。因为这时 k \ge 2，数组开 \log_2 10^9 \approx 30 就行。
注意预处理边权时 k 可能较大，开 long long。图中原本边权 w_i \le 10^9，所以一旦 p_i > 10^9 就停止处理。
然后直接跑最短路就行了。但是蒟蒻爆炸了，赛时 Runtime Error 10。
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using PII = pair<int, int>;
using i32 = int32_t;
using i64 = int64_t;
using ui32 = uint32_t;
using ui64 = uint64_t;
int _;
namespace swate {
inline int read() {int s = 0, w = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w *= -1;ch = getchar();}while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;}
inline i64 read2() {i64 s = 0, w = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w *= -1;ch = getchar();}while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;}
inline void write(i64 x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) write(x / 10); putchar(x % 10 + '0');}
const int N = 1e5 + 5, M = 2e5 + 5;
int n, m, k, s, t;
vector<pair<int, i64> > G[N];
i64 dis[N][35];
bool vis[N][35];
i64 p[35], f = 30;
inline void init() {
}
queue<PII> qu;
inline void bfs1() {
dis[s][0] = 0;
qu.push({s, 0});
while (!qu.empty()) {
PII x = qu.front();
int u = x.fi, d = x.se;
qu.pop();
if (vis[u][d]) continue;
vis[u][d] = 1;
for (auto it : G[u]) {
int v = it.fi;
i64 w = it.se;
if (d < f && p[d] > 0 && dis[v][d + 1] > dis[u][d] + p[d]) {
dis[v][d + 1] = dis[u][d] + p[d];
qu.push({v, d + 1});
}
if (dis[v][d] > dis[u][d] + w) {
dis[v][d] = dis[u][d] + w;
qu.push({v, d});
}
}
}
}
inline void bfs2() {
qu.push({s, 0});
while (!qu.empty()) {
PII x = qu.front();
int u = x.fi, d = x.se;
qu.pop();
if (u == t) {
cout << d;
return ;
}
for (auto it : G[u]) {
int v = it.fi;
qu.push({v, d + 1});
}
}
}
inline void solve() {
n = read(), m = read(), k = read();
for (int i = 1, u, v; i <= m; ++i) {
i64 w;
u = read(), v = read(), w = read2();
G[u].push_back({v, w});
G[v].push_back({u, w});
}
s = read(), t = read();
if (k == 1) {
bfs2();
return ;
} else {
p[0] = 1;
for (int i = 1; i <= 30; ++i) {
p[i] = p[i - 1] * k;
if (p[i] < 0 || p[i] > 1000000000) {
f = i;
break;
}
}
memset(dis, 0x3f, sizeof dis);
bfs1();
i64 ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= f; ++i) {
ans = min(ans, dis[t][i]);
}
write(ans);
}
}
}
//#define Test
i32 main() {
freopen("sum.in", "r", stdin);
freopen("sum.out", "w", stdout);
#ifdef Test
cin >> _;
#else
_ = 1;
#endif
for (int i = 1; i <= _; ++i) {
swate::init();
swate::solve();
}
return 0;
}
这里总结一下死因：
subtask 4是 k=1，炸了因为没有判环，在跑 bfs 时应该打vis标记。subtask 2wa 了，原因很简单，我写的是普通队列，一个点可以可以有多条边通向，所以只要把下面的删掉就可以 AC。
if (vis[u][d]) continue;
vis[u][d] = 1;
但是这样不会死循环吗？不会，因为边至多 30 条，不会死循环。这样甚至比用优先队列的跑得快。