A22732.跑步

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

跑步是一项有意思的运动,尤其是可以开发人的脑筋。常神牛很喜欢跑步。
常神牛跑步的场地是一个多边形(边数≤20,每个顶点用英文大写字母表示),并且在这个多边形内部,还会有一些小道,连接两个不相邻的顶点。所有的边长和小道都是双向通行的举例来说,下面一个图:

假设常神牛从A点跑到D点,最短的路径是A-E-D(长度为6)。

现在告诉你多边形的边数n,多边形每条边的长度,多边形内的连线数k,每条连线的两个端点及长度,以及起始点和结束点,请你输出最短路径的长度。但是常神牛有点强迫症,如果两点之间有多条道路直接连接,他会选择最长的那条。

注意:输入数据不保证起点和终点不同,也不保证小道的起点和终点不同。在读入过程中,如果两点之间有多条小道,那么它们间的距离为这些小道的最大值。所以,如果读入一个小道起点和终点相同,那么这个点到它本身的距离不为0。

输入格式

输入文件为run.in。

第一行,2个数,n,k。

第二行,n个数,分别表示多边形每条边的长度(按顺时针次序依次给出,即分别为AB,BC,CD,DE……的长度)。

以下k行,每行两个字母和一个数,两个字母表示该连线的起止点,数字表示长度。

最后一行,两个字母,分别为他跑步的起点和终点。

所有的一行的字母、数字之间用一个空格隔开。

输出格式

输出文件为run.out。

一行,一个数,表示最短路的长度。

输入输出样例

  • 输入#1

    5 2
    6 4 5 4 2
    A D 7
    E B 8
    A D

    输出#1

    6

说明/提示

对于20%的数据,k=0;

对于50%的数据,k≤10;

对于100%的数据,1≤n≤20,0≤m≤50,k≤100,所有路径长度均不大于1000。

首页