传统题 1000ms 256MiB

互帮助

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

互帮助

题目描述

nn个小朋友,编号从1n1\sim n

他们之间有些人相互认识。

现在他们遇到了一道题目,其中有些人会做,有些人不会做。

每对相互认识的人之间都有一个交流时间(单位:分钟)。

如果一个人会做这道题,他会教自己认识的且不会做这道题小朋友们做这道题,教题花费的时间是他和这个小朋友的交流时间。他可以同时和多个认识的小朋友们一起交流。

如果一个人学会了题目之后,他也立刻会去教自己认识的且不会做这道题的小朋友们。

请问要经过多少分钟所有的小朋友都能会这道题?

输入格式

第一行输入两个正整数n,mn,m表示有nn个小朋友,有mm对人相互认识。

第二行一个长度为nn的只包含'0'和'1'的字符串 ss。'0'表示第ii个小朋友不会这题,'1'表示第ii个小朋友会这题。

接下来mm行,每行三个整数u,v,wu,v,w表示uuvv之间的交流时间为ww分钟。

输出格式

输出一个整数表示经过多少分钟之后所有的小朋友都会这题。

如果无论如何都不能够使所有的小朋友会这道题,输出"-1"(不含引号)。

样例 #1

样例输入 #1

5 5
10001
1 5 2
5 2 3
5 3 1
2 4 2
1 4 10

样例输出 #1

5

样例 #2

样例输入 #2

3 1
100
2 3 4

样例输出 #2

-1

提示

对于所有数据满足$1\le n\le 100,1\le m\le \min\left(\cfrac{n(n+1)}{2},1000\right),1\le u,v\le n,u\neq v,1\le w\le 100$。保证每对相互认识的人都不相同。

5%5\%的数据满足字符串的字符均为'1'。

5%5\%的数据满足字符串的字符均为'0'。

30%30\%的数据满足ww的值均为相同的值。

样例11: 第一个和第五个小朋友刚开始就会这题,一开始他们开始教自己认识且不会这题的小朋友。

11分钟过去后,33号小朋友学会了这题,但是他没有认识且不会这题的小朋友了。

33分钟过去后,22号小朋友学会了这题,他也开始教自己认识且不会这题的小朋友。

55分钟过去后,44号小朋友也学会了这题。(22号小朋友学会后教了他22分钟)

这时候所有的小朋友都会这道题了。

样例22

2,32,3号小朋友一直都没法学会这题。

算法技术测试

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-10-19 14:30
结束于
2023-10-19 18:30
持续时间
4 小时
主持人
参赛人数
1