• [H] Tom and Jerry

  • 时间限制: 2000 ms 内存限制: 65535 K
  • 问题描述
  • The winter vacation is coming , Tom and Jerry would go home together. Tom and Jerry live in America . America have N towns and M single-way roads connecting the towns, and it costs Ti time pass through the i-th single-way roads. Maybe there are multiple single-way roads between two towns .
    They start from town S , and theirs home is in town T. They both want to go home by the path costs minimal time , but ... as you know Tom is a stupid cat, he only know the number is smaller than 10. In another word , in the view of Tom , 98 is equal to 8, 62 is equal to 2, 98 plus 62 equas 0, 3 plus 9 equals 2. So the minimal time in Tom's view is different with you. In Tom's opinion , the minimal time is the time's most right digit is minimal. For example, 10 is smaller than 6 .

    Jerry is a clever mouse , his mathematical ability is as nice as human . But he is a mouse after all , he is afraid of Tom . So he must find a path to make Tom satisfied first .

    If there are multiple paths with which Tom is satisfied , Jerry will find a path which costs minimal time ( in Jerry's view ). So can you help Jerry ?

  • 输入
  • The input contains several test cases.
    The first line contains two integers N(1 <= n <= 100 ), M( 1 <= m <= 1000 ).
    The following line contains two integers S , T( 1 <= S , T <= n ) , meaning the start and the destination .
    The following m lines each contains three integers u, v (1<=u,v<=n), t(1 <= t <= 1000 ) , meaning there is a single-way road from town u to v, which costs t time ( u and v not necessarily different ). The roads are numbered from 1 to m according to the order of the input.
    The input will be terminated by EOF.
  • 输出
  • For each test cases .
    Output the minimal time (in Jerry's view ) you find .
    If Tom and Jerry can't go home anyway , output "Sorry"
  • 样例输入
  • 3 3
    1 3
    1 2 12
    1 3 3
    2 3 8
    3 3
    1 3
    1 2 12
    1 3 10
    2 3 8
    3 2
    1 3
    1 2 12
    2 1 12
  • 样例输出
  • 20
    10
    Sorry
  • 提示
  • 来源
  • Lisz@ZAFU
  • 操作

显示春菜