• [1150] Elective Course

  • 时间限制: 5000 ms 内存限制: 65535 K
  • 问题描述
  • XadillaX has chosen some elective courses.
    Some courses have relation. For example:
    Course A can be the pre-course of Course B, and you need to spend S spirit to transform Courese A to Course B. Opposite, B can be the pre-course either and he need to spend S spirit as well.

    Now give you N courses and their relation. XadillaX choose a course to learn at first, and you should tell him the least spirit he have to spend to finish all the course.
    You can consider that all the courses have relation either direct or not direct.

  • 输入
  • This problem has several cases.
    The first line of each case contains two integers N and M (0 < N <= 1000, 0 <= M < 100000), indicates the number of courses and the number of relations.
    Then follow N lines. Each line is the name of a course, no longer than 20, only contains uppercase, lowercase letters and digits.
    Next M lines indicates M relations. Each line contains two courses' name and the spirit S (0 <= S <= 1000) XadillaX need to spend to transform between these two courses.
    The last line is a course name, indicates the first course XadillaX will take.
  • 输出
  • For each case, you should output the minimum spirit XadillaX will spend after finish all the course. If XadillaX can't transform to all the courses by learning the first course, you should output "No".
  • 样例输入
  • 3 3
    A
    B
    C
    A B 1
    B C 3
    C A 2
    A
    
  • 样例输出
  • 3
    
  • 提示
  • XadillaX takes class A at first. Let A be the pre-course when he takes B. And let A be the pre-course when
    he takes C.
    
  • 来源
  • XadillaX
  • 操作

显示春菜