Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2011
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2011
Galactic Taxes
By Rafael Armando Garcia Gomez 
Colombia
Timelimit: 1
The year is 2115. The Interplanetary Commercial Planning Center (ICPC) is supported by the Autonomous Communication Ministry (ACM). A commercial operation is performed executing transactions between connected ACM offices throughout the galaxy. The execution of a transaction between two connected ACM offices involves a nonnegative tax whose value increases, or decreases, continuously as a linear function A × t + B of time t, where t is a real number measured in minutes during the day (0 ≤ t ≤ 24 × 60).
The total tax of a commercial operation performed between a source ACM office and a destination ACM office at some time t, is calculated as the minimum possible sum of the taxes of the xecuted transactions between the ACM offices visited along some path from the source ACM office to the destination ACM office. The tax of each transaction is calculated at the same time t. Since the tax of the transactions between connected ACM offices is continually changing during the day, it would be better to perform the commercial operation at some specific time in the day, in order to maximize the collected tax. At that time, ACM decides to perform the commercial operation, and not before or after.
Your task is to write a program that receives as input the description of the ACM office network and returns as output the maximum total tax of the commercial operation that can be achieved during the day, that is, the maximum total tax that ACM can collect.
Input
The first line contains two integers N and M, representing respectively the number of ACM offices in the network, and the number of connections (2 ≤ N ≤ 1000 and 1 ≤ M ≤ 104 ). The ACM offices are identified with distinct integers from 1 to N, being 1 the source ACM office and N the destination ACM office. Each of the next M lines describes a connection with four integers I, J, A and B, indicating that there is a bidirectional connection between office I and office J (1 ≤ I < J ≤ N), such that the tax of a transaction executed between office I and office J at time t is defined by the formula A × t + B (−100 ≤ A ≤ 100 and 0 ≤ B ≤ 10^6 ). Taxes are non-negative, so A × t + B ≥ 0 for 0 ≤ t ≤ 24×60. There is at most one connection between each pair of ACM offices, and there is at least one path between the source ACM office and the destination ACM office.
Output
Output a line with a rational number representing the maximum total tax that ACM can collect. The result must be output as a rational number with exactly five digits after the decimal point, rounded if necessary.
| Input Samples | Output Samples |
|
2 1 |
1440.00000 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 1e3 + 1;
const int MAXM = 1e2 + 1;
const double INF = 1e18;
const double EPS = 1e-12;
int grafo[MAXN][MAXM], grau[MAXN], n, m, nafila[MAXN];
double A[MAXN][MAXM], B[MAXN][MAXM], dist[MAXN];
double SPFA(double time) {
for (int i = 1; i < = n; i++) {
dist[i] = INF;
nafila[i] = 0;
}
dist[1] = 0;
nafila[1] = 1;
queue < int> fila;
fila.push(1);
while (!fila.empty()) {
int davez = fila.front();
fila.pop();
nafila[davez] = 0;
for (int i = 0; i < grau[davez]; i++) {
double custo = A[davez][i] * time + B[davez][i];
int proximo = grafo[davez][i];
if (dist[davez] + custo < dist[proximo]) {
dist[proximo] = dist[davez] + custo;
if (!nafila[proximo]) {
nafila[proximo] = 1;
fila.push(proximo);
}
}
}
}
return dist[n];
}
int main() {
while (scanf("%d %d", &n, &m) != EOF) {
for (int i = 1; i < = n; i++) {
grau[i] = 0;
}
for (int i = 1; i < = m; i++) {
int u, v;
double ai, bi;
scanf("%d %d %lf %lf", &u, &v, &ai, &bi);
grafo[u][grau[u]] = v;
A[u][grau[u]] = ai;
B[u][grau[u]++] = bi;
grafo[v][grau[v]] = u;
A[v][grau[v]] = ai;
B[v][grau[v]++] = bi;
}
double ini = 0.0, fim = 1440.0, meio1, meio2;
while (fim - ini > EPS) {
meio1 = ini + (fim - ini) / 3.0;
meio2 = fim - (fim - ini) / 3.0;
if (SPFA(meio1) - EPS < SPFA(meio2)) {
ini = meio1 + EPS;
} else {
fim = meio2 - EPS;
}
}
printf("%.5lf\n", SPFA(ini));
}
return 0;
}
Input
1 2 1 0
Output