http://icpc2010.honiden.nii.ac.jp/domestic-contest/problems#section_E

gistfile1.rb

require 'scanf'
require 'pp'

class Node
  def initialize(id)
    @id = id
    @edges = Array.new
    @done = false
    @word = nil
    @from = nil
  end
  attr_accessor :id, :edges, :done, :word, :from
end

def dijkstra(nodes, start)
  nodes[start].word = ""
  while true
    donenode = nil
    nodes.each do |node|
      if node.done or (!node.word) then
        next
      end
      if !donenode or node.word < donenode.word then
        donenode = node
      end
    end

    break if !donenode

    donenode.done = true
    donenode.edges.each do |edge|
      to,word = edge
      word = donenode.word + word
      if (!nodes[to].word) or (word < nodes[to].word) then
        nodes[to].word = word
        nodes[to].from = donenode.id
      end
    end
  end
end

def create_nodes(file,arg)
  num_nodes,arrows,star,gold = arg
  nodes = Array.new(num_nodes){|i| Node.new(i)}
  arrows.times do
    from, to, word = file.readline.scanf("%d%d%s")
    nodes[from].edges << [to,word]
  end
  nodes.each do |n|
    next if n.edges.empty?
    n.edges.sort!
    if n.id == n.edges.first[0]
      n.edges.clear
    end
  end
  nodes
end

def main
  f = File.open(ARGV.shift)
  while !f.eof?
    n,a,s,g = f.readline.split.map{|i| Integer(i)}
    exit if [n,a,s,g].uniq == [0]
#    p [n,a,s,g]
    nodes = create_nodes(f, [n,a,s,g])
    dijkstra(nodes,s)
#    pp nodes
    puts nodes[g].word ? nodes[g].word: "NO"
  end
end

main