[UVa] 10436 - Cheapest way

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10436 - Cheapest way
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Floyed Warshal Algorithm
Verdict           : Accepted
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define inf           123456789
 
static const int maxn = 25;
 
int city_toll[maxn];
int matrix[maxn][maxn];
int Next[maxn][maxn];
 
map <string, int> Map;
string rMap[maxn];
 
inline void init()
{
    for (int i = 1; i < maxn; i++)
    {
        for (int j = 1; j < maxn; j++)
        {
            matrix[i][j] = inf;
            Next[i][j] = j;
        }
    }
}
 
inline void floyed_warshal(int n)
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int w = matrix[i][j];
                int W = matrix[i][k] + matrix[k][j] - city_toll[k];
                if (w > W)
                {
                    matrix[i][j] = W;
                    Next[i][j] = Next[i][k];  // path printing
                }
            }
        }
    }
}
 
inline void path_print(int src, int des)
{
    vector <int> path;
    path.push_back(src);
    while (src != des)
    {
        src = Next[src][des];
        path.push_back(src);
    }
    int len = path.size();
    for (int i = 0; i < len; i++)
    {
        cout << rMap[ path[i] ];
        if (i+1 == len) cout << endl;
        else cout << " ";
    }
    return;
}
 
inline double getCost(int tCost, int tPass)
{
    double tVal = tCost * 1.0 + (tCost * 1.0 / 10.0);
    double have_to_bear = tVal / (double)tPass;
    return have_to_bear;
}
 
 
int main()
{
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
 
        init();
        int tCity, toll;
        string cityName;
        cin >> tCity;
        for (int i = 1; i <= tCity; i++)
        {
            cin >> cityName >> toll;
            Map[cityName] = i;
            rMap[i] = cityName;
            city_toll[i] = toll;
            matrix[i][i] = toll;   // same city
        }
        int tRoad;
        cin >> tRoad;
        string city1, city2;
        int kl;
        for (int i = 1; i <= tRoad; i++)
        {
            cin >> city1 >> city2 >> kl;
            int u = Map[city1];
            int v = Map[city2];
            kl    = kl * 2;
            matrix[u][v] =  matrix[v][u]  = kl + city_toll[u] + city_toll[v];
        }
        floyed_warshal(tCity);
        cout << "Map #" << tcase << endl;
        int Q, passanger;
        cin >> Q;
        for (int q = 1; q <= Q; q++)
        {
            cin >> city1 >> city2 >> passanger;
            int src = Map[city1];
            int des = Map[city2];
            int tCost = matrix[src][des];
            cout << "Query #" << q << endl;
            path_print(src, des);
            cout << "Each passenger has to pay : "
                 << fixed << setprecision(2)
                 << getCost(tCost, passanger) << " taka" << endl;
        }
        if (tcase < tc) cout << endl;
        Map.clear();
    }
    return 0;
}