[UVa] 13010 - Galactic taxes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13010 - Galactic taxes
Source            : UVa Online Judge
Category          : Graph Theory, Search
Algorithm         : spfa, Ternary Search
Verdict           : Accepted  

#include <bits/stdc++.h>  
   
using namespace std;  
   
#define inf             1e13  
   
static const int maxn = 1000 + 5;  
   
struct node  
{  
    int v, A, B;  
    node() {}  
    node(int v, int A, int B)  
    {  
        this->v = v;  
        this->A = A;  
        this->B = B;  
    }  
};  
   
vector <node> g[maxn];  
   
int N, M;  
double dist[maxn];  
bool inQueue[maxn];  
   
double SPFA(double t)  
{  
    for (int i = 1; i < maxn; i++)  
    {  
        dist[i] = inf;  
        inQueue[i] = 0;  
    }  
    queue <int> PQ;  
    PQ.push(1);  
    dist[1] = 0.0;  
    inQueue[1] = 1;  
    while (!PQ.empty())  
    {  
        int u = PQ.front(); PQ.pop();  
        inQueue[u] = 0;  
        for (auto &it : g[u])  
        {  
            double cost = (double)it.A * t + (double)it.B;  
            int v = it.v;  
            if (dist[v] > dist[u] + cost)  
            {  
                dist[v] = dist[u] + cost;  
                if (!inQueue[v])  
                {  
                    inQueue[v] = 1;  
                    PQ.push(v);  
                }  
            }  
        }  
    }  
    return dist[N];  
}  
   
void ternary_search()  
{  
    double low = 0.0;  
    double high = 1440.0;  
    double ans = -inf;  
    for (int tol = 0; tol < 300; tol++)  
    {  
        double mid1 = low + (high - low) / 3.0;  
        double mid2 = high - (high - low) / 3.0;  
        double fmid1 = SPFA(mid1);  
        double fmid2 = SPFA(mid2);  
        ans = max(ans, max(fmid1, fmid2));  
        if (fmid1 < fmid2) low = mid1;  
        else high = mid2;  
    }  
    cout << fixed << setprecision(5) << ans << endl;  
}  
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    while (cin >> N >> M)  
    {  
        for (int i = 0; i < M; i++)  
        {  
            int u, v, A, B;  
            cin >> u >> v >> A >> B;  
            g[u].push_back({v, A, B});  
            g[v].push_back({u, A, B});  
        }  
        ternary_search();  
        for (int i = 0; i < maxn; i++) g[i].clear();  
    }  
}