Free ticket, INOI 2014

Problem Description

Question : Free Ticket, INOI 2014

Submit Code : Codechef

Prerequisites

Floyd-Warshall Algorithm

Solution

Nikhil has to choose two stations whose minimum flight price is maximum in every possible station pairs that can be chosen. So, First, we will find minimum price between every two stations and then take maximum among those which will be our answer.

It is straight forward problem of Floyd-Warshall Algorithm (The Shortest Path), just nodes have been replaced with stations and distances with price of flights.

Code

#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000

int main(){
    int n, m;
    cin >> n >> m;
    int price[n+1][n+1];
    int x, y, p;

    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            price[i][j] = INF;
    
    for(int i=0;i<m;i++){
        cin >> x >> y >> p;
        price[x][y] = p;
        price[y][x] = p;
    }
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                price[i][j] = min(price[i][j], price[i][k] + price[k][j]);
    
    int ans = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i != j)
                ans = max(ans, price[i][j]);
    
    cout << ans;

    return 0;
}