题目传送门(BZOJ)

题解 :

$K$很小,考虑分层图

把用掉一次免费机会视作走到下一层, 先建出来$K+1$层图, 对于每条边, 从层$i$到层$i+1$连接权为0的单向边

对于所有层的$n(T)$,向下一层的对应$T$连一条0权边

这两道题的区别就是从$S$到$T$还是从$1$到$n$没什么大的不一样.

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;#define mp(a,b) make_pair(a,b)#define sec secondconst int N = 20000;const int M = 60000;struct node { int next, to, val;}e[(M<<1)*60];int n, m, k;int cnt, head[N*31];int dis[N*31];void add_edge(int a, int b, int c) { e[++cnt].to = b; e[cnt].val = c; e[cnt].next = head[a]; head[a] = cnt;}int s, t;priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;bool vis[N*31];void Dijkstra() { memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; q.push(mp(0, s)); while(!q.empty()) { int u = q.top().sec; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u];i;i = e[i].next) { if(dis[e[i].to]>dis[u]+e[i].val) { dis[e[i].to] = dis[u]+e[i].val; q.push(mp(dis[e[i].to], e[i].to)); } } } printf("%d\n", dis[n*k+t]);}int main() { scanf("%d%d%d%d%d", &n, &m, &k, &s, &t); for(int i = 1; i <= m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); for(int j = 0; j <= k; j ++ ) { add_edge(b+j*n, b+j*n, 0); add_edge(a+j*n, a+j*n, 0); add_edge(b+j*n, a+j*n, c); add_edge(a+j*n, b+j*n, c); add_edge(b+j*n, a+(j+1)*n, 0); add_edge(a+j*n, b+(j+1)*n, 0); } } Dijkstra();}