131 lines
2.9 KiB
Plaintext
131 lines
2.9 KiB
Plaintext
import Algorithms as algo;
|
|
import Mathematics as math;
|
|
import Text as text;
|
|
|
|
class Edge {
|
|
_to = none;
|
|
_name = none;
|
|
_cost = none;
|
|
constructor( to_, name_, cost_ ) {
|
|
_to = to_;
|
|
_name = name_;
|
|
_cost = real( cost_ );
|
|
}
|
|
to_string() {
|
|
return ( "{}<{}>".format( _name, _cost ) );
|
|
}
|
|
}
|
|
|
|
class Path {
|
|
_id = none;
|
|
_from = none;
|
|
_cost = none;
|
|
_names = none;
|
|
constructor( toName_, ids_, names_ ) {
|
|
_id = ids_[toName_];
|
|
_names = names_;
|
|
_cost = math.INFINITY;
|
|
}
|
|
less( other_ ) {
|
|
return ( _cost < other_._cost );
|
|
}
|
|
update( from_, cost_ ) {
|
|
_from = from_;
|
|
_cost = cost_;
|
|
}
|
|
to_string() {
|
|
return ( "{} via {} at cost {}".format( _names[_id], _from != none ? _names[_from] : none, _cost ) );
|
|
}
|
|
}
|
|
|
|
class Graph {
|
|
_neighbours = [];
|
|
_ids = {};
|
|
_names = [];
|
|
add_node( name_ ) {
|
|
if ( name_ ∉ _ids ) {
|
|
_ids[name_] = size( _names );
|
|
_names.push( name_ );
|
|
}
|
|
}
|
|
add_edge( from_, to_, cost_ ) {
|
|
assert( ( from_ ∈ _ids ) && ( to_ ∈ _ids ) );
|
|
from = _ids[from_];
|
|
to = _ids[to_];
|
|
if ( from >= size( _neighbours ) ) {
|
|
_neighbours.resize( from + 1, [] );
|
|
}
|
|
_neighbours[from].push( Edge( to, to_, cost_ ) );
|
|
}
|
|
shortest_paths( from_ ) {
|
|
assert( from_ ∈ _ids );
|
|
from = _ids[from_];
|
|
paths = algo.materialize( algo.map( _names, @[_ids, _names]( name ) { Path( name, _ids, _names ); } ), list );
|
|
paths[from].update( none, 0.0 );
|
|
todo = algo.sorted( paths, @(x){-x._cost;} );
|
|
while ( size( todo ) > 0 ) {
|
|
node = todo[-1]._id;
|
|
todo.resize( size( todo ) - 1, none );
|
|
if ( node >= size( _neighbours ) ) {
|
|
continue;
|
|
}
|
|
neighbours = _neighbours[node];
|
|
for ( n : neighbours ) {
|
|
newCost = n._cost + paths[node]._cost;
|
|
if ( newCost < paths[n._to]._cost ) {
|
|
paths[n._to].update( node, newCost );
|
|
}
|
|
}
|
|
todo = algo.sorted( todo, @(x){-x._cost;} );
|
|
}
|
|
return ( paths );
|
|
}
|
|
path( paths_, to_ ) {
|
|
assert( to_ ∈ _ids );
|
|
to = _ids[to_];
|
|
p = [to_];
|
|
while ( paths_[to]._from != none ) {
|
|
to = paths_[to]._from;
|
|
p.push( _names[to] );
|
|
}
|
|
return ( algo.materialize( algo.reversed( p ), list ) );
|
|
}
|
|
to_string() {
|
|
s = "";
|
|
for ( i, n : algo.enumerate( _neighbours ) ) {
|
|
s += "{} -> {}\n".format( _names[i], n );
|
|
}
|
|
}
|
|
}
|
|
|
|
main() {
|
|
g = Graph();
|
|
confStr = input();
|
|
if ( confStr == none ) {
|
|
return ( 1 );
|
|
}
|
|
conf = algo.materialize( algo.map( text.split( confStr ), integer ), tuple );
|
|
assert( size( conf ) == 2 );
|
|
for ( _ : algo.range( conf[0] ) ) {
|
|
line = input();
|
|
if ( line == none ) {
|
|
return ( 1 );
|
|
}
|
|
g.add_node( line.strip() );
|
|
}
|
|
for ( _ : algo.range( conf[1] ) ) {
|
|
line = input();
|
|
if ( line == none ) {
|
|
return ( 1 );
|
|
}
|
|
g.add_edge( algo.materialize( text.split( line.strip() ), tuple )... );
|
|
}
|
|
print( string( g ) );
|
|
paths = g.shortest_paths( "a" );
|
|
for ( p : paths ) {
|
|
print( "{}\n".format( p ) );
|
|
}
|
|
print( "{}\n".format( g.path( paths, "e" ) ) );
|
|
print( "{}\n".format( g.path( paths, "f" ) ) );
|
|
}
|