[UVA] 12047 - Highest Paid Toll
Problem H - Highest Paid Toll
In Dhaka there are too many vehicles. So, the result is well known, yes, traffic jam. So, mostly people have to spend a long time in the roads to go from one place to another. But who knows, what can be the solution.
Now, the Casual Students in Engineering from Dhaka University (CSEDU) have finally found a solution to this problem. The idea is to make all the roads one way. That means a vehicle can go through the road in one way. And to make the number of vehicles low, each vehicle has to pay a toll to use a road.
Now you are a member of CSEDU, and you want to go from a place s to another place t. And you have a total of p taka in your pocket. Now you want to find the road that takes the highest toll, to go from s to t. Remember that you can't use more than p taka.
For the picture above, s = 1, t = 5 and p = 10. There are three paths from 1 to 5 -
Path 1: 1 -> 2 -> 5, total toll = 11 (> p)
Path 2: 1 -> 3 -> 5, total toll = 9 (≤ p), 6 is the maximum toll
Path 3: 1 -> 4 -> 5, total toll = 9 (≤ p), 5 is the maximum toll
So the maximum toll for a road of all of the paths having total toll ≤ p is 6.
Input
The first line of the input file contains an integer T (T ≤ 50) which denotes the total number of test cases.
The description of each test case is given below:
Each case starts with five integers N (2 ≤ N ≤ 10000), M (1 ≤ M ≤ 100000), s (1 ≤ s ≤ N), t (1 ≤ t ≤ N) and p (1 ≤ p ≤ 106). Then there are M lines each containing three integers u, v and c. u and v are place numbers and there is a road from u to v (1 <= u, v ≤ N, u ≠ v) and c (0 ≤ c ≤ 105) is the toll needed for that road.
Output
For each line of input produce one line of output containing r. Where r is the maximum toll needed for a road to go from s to t where the path doesn't need more than p taka toll or -1 if there is no such road.
Sample Input
2 5 6 1 5 10 1 2 7 2 5 4 1 3 6 3 5 3 1 4 5 4 5 4 2 1 1 2 10 1 2 20
Sample Output
6 -1
Special Thanks: Jane Alam Jan
Next Generation Contest 6
題目描述：
找到任何一條路徑總花費小於等於 p 中，路徑中其中一條使用的權重最大值為何？
題目解法：
題目給定的是有向圖，因此對於一組邊 (i, j), 權重是 w(i, j)。
找到 st->i 的最短路 + w(i, j) + j->ed 的最短路 <= p，
則可以認為 w(i, j) 可以當作其中一解。
因此要先找出 st 為起點到所有點的距離，以及在反向圖中，找到所有 ed 到所有點的距離。
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
struct E {
int to, v;
E(int a, int b):
to(a), v(b) {}
};
vector<E> g[10005], vg[10005];
#define oo 1000000000
void spfa(int st, int n, int dist[], int cut, vector<E> g[]) {
int i, tn;
static int inq[10005] = {};
for(i = 1; i <= n; i++)
dist[i] = oo;
queue<int> Q;
dist[st] = 0;
Q.push(st);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
inq[tn] = 0;
if(dist[tn] >= cut) continue;
for(i = g[tn].size()-1; i >= 0; i--) {
if(dist[g[tn][i].to] > dist[tn]+g[tn][i].v) {
dist[g[tn][i].to] = dist[tn]+g[tn][i].v;
if(inq[g[tn][i].to] == 0) {
inq[g[tn][i].to] = 1;
Q.push(g[tn][i].to);
}
}
}
}
}
int main() {
int n, m, s, t, p;
int testcase;
int i, j, k, x, y, v;
int fromS[10005], fromT[10005];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d %d %d", &n, &m, &s, &t, &p);
for(i = 1; i <= n; i++)
g[i].clear(), vg[i].clear();
for(i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &v);
g[x].push_back(E(y, v));
vg[y].push_back(E(x, v));
}
spfa(s, n, fromS, p, g);
spfa(t, n, fromT, p, vg);
int ret = -1;
for(i = 1; i <= n; i++) {
for(j = g[i].size()-1; j >= 0; j--) {
if(fromS[i]+fromT[g[i][j].to]+g[i][j].v <= p)
ret = max(ret, g[i][j].v);
}
}
printf("%d\n", ret);
}
return 0;
}