• [I] I Will Take TT Home

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • TT often go to the West Campus to see Mr.Cai in the evening.

    When TT want to go back to the Eest Campus it's pretty late, So Mr.Cai will take TT home in oder to protect she.

    Mr.Cai will take TT to Eest Campus, but there are some others who come with TT.

    They want leave Mr.Cai and TT alone, so they decided that they don't take the road Mr.Cai traveled.

    There are a lot of station between Eest Campus and Eest Campus. Each station connected by road.

    The road contain the station.

  • 输入
  • First line contain a integer T (0 < T <= 20) means the test case.
    For each case, There are two integers W, E (1 <= W < E <= 200) in a line means to the West Campus station number and East Campus station number.
    And then there are a integer M (2 <= M <= 200) means to the number of station. And the station numbered 1 to M.
    the follow line contain M integers means you go through the ith station you have to cost Mi (0 < Mi < 200) minutes.
    And then there are a integer N (0 < N < 500) mean the road's number
    The follow N lines, there are X, Y (1 <= X, Y <= 200) means there are a road from X to Y. It guarantee X != E and Y != W.

    PS: All these people start from West Campus and arrive the Eest Campus at the same time. It means they can just pay
    once when go through West Campus and Eest Campus.

  • 输出
  • For each test case, print the minimum money will cost. If someone can't arrive the Eest Campus print "T~T" to instead.
  • 样例输入
  • 3
    1 4
    4
    1 2 3 4
    5
    1 3
    1 2
    3 2
    2 4
    3 4
    
    1 4
    4
    1 2 3 4
    3
    1 4
    1 3
    1 2
    
    1 4
    4
    1 2 3 4
    6
    1 3
    1 2
    1 4
    2 3
    2 4
    3 4
  • 样例输出
  • 10
    T~T
    7
    
  • 提示
  • 来源
  • Monkeyde17
  • 操作

显示春菜