Uva Problem 544 - Heavy Cargo Solution (C++)

Welcome:

The question to the problem can be found here:


Explanation:

1. The truck size is not needed since the problem can be solved using the lowest cost of path.
2. Use Map function to dynamically point city name(string) to Index(int).
3.++Index means value is increased and then assigned.
4. Use a Modified Floyd Warshal Algorithm as shown below.
5. Every Node in the array d now point to the minimum cost.
6. Finally the source to destination of the array is printed.
7.Happy Coding

Code:

#include<bits/stdc++.h>
using namespace std;
#define clr(a,replace) memset(a,replace,sizeof(a))
#define INF 99999
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define PB push_back
#define MAX 100000
#define LL long long
#define pf printf

int Case=0;
int main(){
//freopen("input.txt","r",stdin);
//   freopen("output.txt","w",stdout);
int n,r;

while(cin>>n>>r){
        if(n==0 && r ==0){
            return 0;
        }

    map<string,int> city;

    string x,y;
    int cost;
    int index=0;
    int d[250][250];
    rep(i,250){
    rep(j,250){
    d[i][j]=-1;
if(i==j){
    d[i][j] =0;
}
    }}
    for(int i=0;i<r;i++){
            cin>>x>>y>>cost;
        if(!city[x]){
            city[x] = ++index;
        }
        if(!city[y]){
            city[y]= ++index;
        }
    d[city[x]][city[y]] =cost;
    d[city[y]][city[x]] =cost;
    }

    for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
           d[i][j]=d[j][i] = max(d[i][j],min(d[i][k],d[k][j]));
        }
    }
    }
Case++;
    string source;
    string destination;
    cin>>source>>destination;
    pf("Scenario #%d\n%d tons\n\n",Case,d[city[source]][city[destination]]);

    city.clear();

}


return 0;}