有k次机会让图中边权值为0,
第一种方法:
建图的时候建立k+1层图, 走了权值为0的边就表示用掉了一次机会, 最后在n, n + n, ...k + n中取最小值
原图链接
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
const int N = 2e6 + 10;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx, dist[N], st[N], n, m;
int s, t, k;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, s});
dist[s] = 0;
while(q.size())
{
auto t = q.top();
q.pop();
int d = t.first, v = t.second;
if(st[v])continue;
st[v] = 1;
for (int i = h[v]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > d + w[i] && !st[j])
{
dist[j] = d + w[i];
q.push({dist[j], j});
}
}
}
}
signed main()
{
memset(h, -1, sizeof h);
memset(dist, 0x3f, sizeof dist);
cin >> n >> m >> s >> t >> k;
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
for(int j = 0; j <= k; j ++)
{
add(a + j * n, b + j * n, c);
add(b + j * n, a + j * n, c);
if(j != k)
{
add(a + j * n, b + (j + 1) * n, 0);
add(b + j * n, a + (j + 1) * n, 0);
}
}
}
dijkstra();
int res = inf;
for(int i = 0; i <= k; i ++)
{
res = min(res, dist[t + i * n]);
}
cout << res << endl;
return 0;
}