Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INF 2139062143
- #define MAX 100
- #define debug(x) cout << #x << " = " << x << endl
- #define fori(i, ini, lim) for(int i= int(ini); i<(int)lim; ++i)
- #define ford(i, ini, lim) for(int i= int(ini); i>=(int)lim; --i)
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> ii;
- typedef pair<int, pair<int, ii> > pii;
- int a, b, K, m, l;
- int dist[MAX+5][15][505];
- vector<ii> adj[MAX+5];
- void dij(int s){
- priority_queue<pii, vector<pii>, greater<pii> > pq;
- dist[s][0][0] = 0; // vertex, k, quilometros left
- pq.push(pii(0,make_pair(s, ii(0,0)))); // weight, vertex, k = how many times the boots were used, quilometros left
- while(!pq.empty()){
- pii cur = pq.top(); pq.pop();
- int u = cur.second.first;
- int w = cur.first;
- int k = cur.second.second.first;
- int isk = cur.second.second.second;
- if(w > dist[u][k][isk]) continue;
- fori(i,0,adj[u].size()){
- ii cadj = adj[u][i];
- int v = cadj.first;
- int nw = cadj.second;
- // do not use the magic boots
- if(dist[u][k][isk] + nw < dist[v][k][isk]){
- dist[v][k][isk] = dist[u][k][isk] + nw;
- pq.push(pii(dist[v][k][isk],make_pair(v, ii(k,0))));
- }
- // is in the middle of the run, so keep runing
- if(isk >= nw && u <= a){
- if(dist[u][k][isk] < dist[v][k][isk-nw]){
- dist[v][k][isk-nw] = dist[u][k][isk];
- pq.push(pii(dist[v][k][isk-nw],make_pair(v, ii(k,isk-nw))));
- }
- }
- // start a new run with the magic boots
- if(k < K && l >= nw){
- if(dist[u][k][0] < dist[v][k+1][l-nw]){
- dist[v][k+1][l-nw] = dist[u][k][0];
- pq.push(pii(dist[v][k+1][l-nw],make_pair(v, ii(k+1,l-nw))));
- }
- }
- //cout << "u: " << u << " v: " << v << " nw: " << nw << " dist[u]: " << dist[u][k][isk] << " dist[v]: " << dist[v][k][isk] << " k: " << k << " isk: " << isk << endl;
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- int t; cin >> t;
- while(t--){
- cin >> a >> b >> m >> l >> K;
- fori(i,0,a+b+1){
- adj[i].clear();
- }
- fori(i,0,m){
- int x, y, w; cin >> x >> y >> w;
- adj[x].emplace_back(y,w);
- adj[y].emplace_back(x,w);
- }
- memset(dist, 0x7F, sizeof(dist));
- dij(a+b);
- int ans = INF;
- fori(j, 0, l){
- fori(i, 0, K+1){
- ans = min(ans, dist[1][i][j]);
- }
- }
- cout << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement