UVA544 Heavy Cargo

Graph, Floyd

출처: UVA UVA544 Heavy Cargo


SOL)
무게를 더 실을 수 있는 경로가 존재한다면 그 경로를 선택


[-] Collapse

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
using namespace std;
const int INF = (1 << 30);
int adj[200][200];
int V, E, idx;
string from, to;
map<string, int> mp;
int u, v, val;

void init(){
    memset(adj, -1, sizeof(adj));
    mp.clear();
    idx = 0;
}

int Mapping(string str){
    if (mp.find(str) == mp.end())
        mp[str] = idx++;
    return mp[str];
}

void Floyd(){
    for (int k = 0; k < V; k++){
        for (int i = 0; i < V; i++){
            for (int j = 0; j < V; j++){
                if (adj[i][j] < min(adj[i][k], adj[k][j]))
                    adj[j][i] = adj[i][j] = min(adj[i][k], adj[k][j]);
            }
        }
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    int testCase = 0;
    while (true){
        cin >> V >> E;
        if (V == 0 && E == 0) break;
        init();
        for (int i = 0; i < E; i++){
            cin >> from >> to >> val;
            u = Mapping(from);
            v = Mapping(to);
            adj[v][u] = adj[u][v] = val;
        }
        cin >> from >> to;
        u = mp[from];
        v = mp[to];
        Floyd();
        cout << "Scenario #" << ++testCase << endl;
        cout << adj[u][v] << " tons" << endl << endl;
    }
}