1. C++, Tobias Fuchs

/* Accepted */

#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>

#define MAX_NODES 100
#define NO_CONNECTION_WEIGHT 0
#define log(msg) ::std::cout << msg << ::std::endl

using ::std::map;
using ::std::string;
using ::std::vector;

class Weight_Strategy
{

private: // Members

vector<string> m_node_names;
map<string,int> m_node_ids;
int m_weight_map[MAX_NODES][MAX_NODES];
unsigned int m_num_cities;
unsigned int m_num_segments;

public: // Ctor

Weight_Strategy(unsigned int num_cities, unsigned int num_segments)
: m_num_cities(num_cities),
m_num_segments(num_segments)
{
for(unsigned int x=0; x<num_cities; ++x) {
for(unsigned int y=0; y<num_cities; ++y) {
m_weight_map[x][y] = NO_CONNECTION_WEIGHT;
}
}
}

public: // Class instance methods

inline void add_connection(string & from, string & to, int weight) {
unsigned int id_from = add_node(from);
unsigned int id_to = add_node(to);
m_weight_map[id_from][id_to] = weight;
m_weight_map[id_to][id_from] = weight;
}

unsigned int resolve(string & from, string & to)
{
unsigned int from_id, to_id;
from_id = node_id_of(from);
to_id = node_id_of(to);

for(unsigned int k=0; k<m_num_cities; ++k) {
for(unsigned int i=0; i<m_num_cities; ++i) {
for(unsigned int j=0; j<m_num_cities; ++j) {
unsigned int val = max( m_weight_map[i][j],
min(m_weight_map[i][k], m_weight_map[k][j]) );
m_weight_map[i][j] = val;
}
}
}
return m_weight_map[from_id][to_id];
}

private: // Helpers

inline const string & node_name_of(int node_id) { return m_node_names[node_id]; }
inline const unsigned char node_id_of(string const & node_name) { return m_node_ids[node_name]; }
inline const unsigned char add_node(string const & node_name) {
unsigned int node_id;
if(m_node_ids.find(node_name) == m_node_ids.end()) { // node name not registered yet
m_node_names.push_back(node_name);
node_id = (unsigned char)(m_node_names.size()-1);
m_node_ids[node_name] = node_id;
}
else {
node_id = m_node_ids[node_name];
}
return node_id;
}
inline static const unsigned int max(unsigned int const a, unsigned int const b) {
return ((a > b)? a : b);
}
inline static const unsigned int min(unsigned int const a, unsigned int const b) {
return ((a < b)? a : b);
}
};

int main(int argc, char * argv[])
{
int weight;
bool exit = false;
string from, to;

unsigned int num_cities, num_segments;
string token;

::std::vector<int> scenarios;

// Read scenarios
while(!exit) {
// Read amount of cities and segments:
::std::cin >> token;
num_cities = atoi(token.c_str());
token.clear();
::std::cin >> token;
num_segments = atoi(token.c_str());
token.clear();

if(num_cities == 0 && num_segments == 0) {
exit = true;
}
else {
bool expecting_cities = true;
// Initialize strategy for every scenario
Weight_Strategy strategy(num_cities, num_segments);
// Read a single connection line:
while(expecting_cities)
{
::std::cin >> token;
from = string(token);
token.clear();

::std::cin >> token;
to = string(token);
token.clear();

getline(::std::cin, token);
if(token.length() > 0) {
weight = atoi(token.c_str());
strategy.add_connection(from, to, weight);
}
else { // No weight given -> Input was path to solve
expecting_cities = false;
}
}
// strategy.print_map();
unsigned int maxpath = strategy.resolve(from, to);
scenarios.push_back(maxpath);
}
}

// Print scenarios here as sequential output, Online Judge doesn't get it otherwise.
for(unsigned int set = 0; set < scenarios.size(); ++set) {
log("Scenario #" << set+1);
log("maximum weight is " << scenarios[set]);
log("");
}

return 1;
}