NK05DSRT - Sa mạc

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define fi first
#define se second
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define INF 1000000000
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<LL> vi;

vvii g;
LL n, m, c;

void enter() {
	scanf("%lld%lld%lld",&n,&m,&c);
	g = vvii(n, vii());
	for(LL i = 0; i < m; ++i) {
		LL u, v, l; scanf("%lld%lld%lld",&u,&v,&l);
		g[--u].push_back(ii(--v, l));
		g[v].push_back(ii(u, l));
	}
}

inline LL ceil(int a, int b) {
	return b <= 0 ? INF : a / b + (a % b != 0);
}

void solve() { //Dijkstra's Algorithm
	vi d = vi(n, INF); d[n-1] = 0;
	priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, n-1));
	while(!qu.empty()) {
		LL du = qu.top().fi, u = qu.top().se; qu.pop();
		if (du > d[u]) continue;
		TR(g[u], it) {
			LL v = it->fi, l = it->se;
			if(du + l <= c) {
				if(du + l < d[v]) qu.push(ii(d[v] = du + l, v));
			} else {
				LL k = ceil(du - c + l, c - l - l);
				if(k != INF && (k+k+1)*l + du < d[v]) qu.push(ii(d[v] = (k+k+1)*l + du, v));
			}
		}
	}
	printf("%lld\n", d.front());
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	LL tc; scanf("%lld", &tc);
	while(tc--) {
		enter();
		solve();
	}
	return 0;
}

Download