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;
}