2015
04-13

# Saving the Princess

As most fairy tales said, unfortunately, our poor princess is trapped in a castle by some bad guys again.

Simple word, we need save her again, because she is so beautiful and graceful that we love her so much. Our country was composed of N cities and M undirected roads, the princess was in the city A, and we were in city 0, the capital. Obviously, only we arrive at the city A first can we save the princess.
However, it’s not a shortest path problem because we had extremely enough time to spend among the roads. What matters was whether we could arrive at the city A.

Perhaps a strange problem, but it’s reasonable because we need food and water while travelling from one city to another, or we just would be died before we can see the princess. To make the situation less complicated, we assumed we always consumed two units of food and one unit of water when we were walking, just like a coefficient multiply the distance we had walked.

But the condition left for us is a little annoyed. As our country was very poor, we could only purchase the food in the capital. What’s more, at any time, the sum of food units and water units we carried can’t exceed the capacity S.
Oh, don’t be despair, please. Also some not too bad news was here. We could rest and collect water as much as possible at any city, and in each city, there were plenty of storages to store food for our later use.

Now, to save our lovely and pitiful princess, how much food we have to purchase in the capital at least?

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with four integers N, M, S, A. Their meanings are the same as the description.
Then M lines follow, each line contains three integers Ai, Bi, Ci, indicating an undirected road from Ai to Bi whose length was Ci.

Technical Specification

1. 1 <= T <= 50
2. 2 <= N <= 1000
3. 1 <= M <= 50000
4. 1 <= S, Ci <= 100000
5. 1 <= A < N
6. 0 <= Ai, Bi < N, Ai != Bi

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with four integers N, M, S, A. Their meanings are the same as the description.
Then M lines follow, each line contains three integers Ai, Bi, Ci, indicating an undirected road from Ai to Bi whose length was Ci.

Technical Specification

1. 1 <= T <= 50
2. 2 <= N <= 1000
3. 1 <= M <= 50000
4. 1 <= S, Ci <= 100000
5. 1 <= A < N
6. 0 <= Ai, Bi < N, Ai != Bi

3
2 1 5 1
0 1 1
2 1 5 1
0 1 2
4 5 20 3
0 1 3
0 2 4
2 3 5
1 3 6
0 3 7

Case 1: 2
Case 2: Poor princess, we will miss you!
Case 3: 30

#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1000
#define max (1<<29)
typedef __int64 ll;
const ll inf = (1ll)<<50;
int t, n, m, s, a, i, j, u, v, w, now, tmp1, tmp2;
int dis[maxn][maxn];
ll best[maxn];
ll cost, k21, k22;
bool vis[maxn];
int q[maxn*maxn];
bool flag;
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &t);
for (int cases = 1; cases <= t; cases++) {
scanf("%d %d %d %d", &n, &m, &s, &a);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dis[i][j] = -1;

for (i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
dis[u][v] = dis[v][u] = w;
}

head = 1; tail = 1; q[1] = a;
for (i = 0; i < n; i++) best[i] = inf;
for (i = 0; i < n; i++) vis[i] = false;

best[a] = 0;vis[a] = true;
for (i = 0; i < n; i++)
if ((dis[now][i] != -1) && (dis[now][i]*3 <= s)) {
if ( best[now]+3*dis[now][i] <= s) {// transport the food in one time
cost = best[now]+2*dis[now][i]; // the food needed to consume
flag = true;
} else {
tmp1 = s-3*dis[now][i]; // at most one can transport in one time
tmp2 = s-5*dis[now][i]; // at most one can transport going in two-way
if(tmp2 > 0){ // take more times
k21 = (best[now]-tmp1)/tmp2; // need k21's two-ways
k22 = (best[now]-tmp1)%tmp2;
cost = 1ll*(s-dis[now][i])*(1+k21)+1ll*(k22!=0)*(k22+4*dis[now][i]);
flag = true;
} else flag = false; //fail
}
if (flag && cost < best[i]){
best[i] = cost;
//printf("%d %d\n", i, cost);
if (!vis[i]) {
vis[i] = true;
q[++tail] = i;
}
}
}
}