Skip to content

11313: 【原1313】太湖旅行

题目

题目描述

author: 柏钧文 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1313

Description

西山风景区是苏州著名的国家级风景区,一到暑假,游客们都蜂拥而至。作为太湖风景区的精华,西山景区吸引人的地方主要在它的群岛风光、花果丛林和名胜古迹。

ginrat对这个地方向往已久,在暑假时忙里偷空出来玩了一次。一到景区,具有特殊观察力的他就开始观察,他发现,景区实际上是由太湖的一部分水域和露出水面的许多小岛构成的,小岛之间由许多桥(或者是堤坝,whatever)连接。ginrat是一个玩起来很有责任心的人,他非常想要逛完每个岛、每个桥,可bj提醒他,网页小组还等着他回去写文档,时间紧迫。根据导游的信息,这里共有n座岛,m座桥,ginrat开跑车经过每个桥或岛的时间很少很少,但他却要在每个桥或岛上面好好欣赏风景,这需要一定的时间。他不会重复在一个岛或桥上面欣赏风景。由于时间紧迫,他也降低了自己的目的。如果一座桥连接的两座岛他都在上面欣赏过了,这座桥上的风景他就认为他已经看过了,如果一座岛周围连接的所有的桥上的风景他都看过了,那么岛上的风景他也不想看了。

现在ginrat需要最少的时间来逛完景区,你能帮他吗?

Input Format

第一行两个整数n和m,分别表示岛屿的数量和桥的数量。

第二行有n个整数,分别表示n个岛屿ginrat观光所需要的时间

第3~m+2行,每行三个整数,表示这座桥连接的两个岛的编号以及ginrat观光这座桥上风景所需要的时间

Output Format

一个整数,ginrat观光所需最少时间

Sample Input

2 1
2 2
1 2 1

Sample Output

1

Hint

n<=500, m<=1500

ginrat每次观光时间不超过100000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!