今日试题
三道难题，我不想放出来……
我屈服了，我放题：
Task 1. 最优检测（test）
题目描述
有一个长度为 n的数组，每个数字为 0、1 中的一个，但你并不知道是多少。
你可以花费 c_{i, j}的代价，查询出区间 i~j的在模 2 意义下的区间和。
求确定出 n个位置上所有数字的最小代价。
输入格式
第一行一个数 n。
接下来 n 行，第 i 行若干整数，表示 c_{i, i~n}。
输出格式
输出一个数，表示最小花费。
数据范围
测试点 1~3：n≤10。
测试点 1~10：1≤n≤2000，c_{i, j}≤10^9。
Task 2. 图的中心（graph）
题目描述
一张 n个点 m 条边的无向连通图，边有长度。
你要找一个位置，定义这个位置到某个点的距离为最短路的长度，你需要最小化该位置
到 n 个点的距离最大值。注意这个位置可以在某条边上。
找到位置后，只需输出到最远的距离即可。
输入格式
第一行两个整数 n、m。
接下来 m 行，每行三个数 u、v、w，表示一条连接 u、v 长度为 w 的边。
输出格式
一个实数表示所求，四舍五入保留 8 位小数。
数据范围
测试点 1~3：n≤50。
测试点 1~10：2≤n≤200，n-1≤m≤n(n-1)/2，边的长度不超过 10^5。
Task 3. 雨中冒险（rain）
题目描述
有 n 个节点，标号为 1~n。m 条双向公路连接着这些节点，其中第 i 条公路连接着 u_i和 v_i，从一端走到另一端需要 w_i 秒。现在，小 Y 打算从学校回到家里。
学校是节点 1，小 Y 家是节点 n，保证存在至少一条从节点 1 到节点 n 的路径。
在第 0 秒，小 Y 身处节点 1，他的目标是尽早到达节点 n。根据天气预报，接下来会有k次暴雨，第 i 次暴雨的时间为第 l_i 秒至第 r_i 秒，保证每次暴雨的时间段互不重叠（包括起止时间）。由于小 Y 忘了带伞，因此在下雨期间，他只能躲在某个节点里面避雨。如果某一个时刻在下暴雨，而小 Y还在某条公路上，那么他会被淋惨。
为了帮助小 Y 尽快回到家，上帝决定实现小 Y 一个愿望。小 Y 可以指定某一条道路，然后这条道路两端的节点将合并成一个节点（合并出的节点拥有原来两个节点的所有出边）。
请你帮小 Y计算，在不被淋惨的前提下最早第多少秒他能回到自己家中？
注：对于一场第 l~r 秒的暴雨，若小 Y 第 r 秒从节点出发，或者第 l 秒到达某个节点，那么他是不会淋到雨的。
输入格式
第一行三个数 n、m、k。
接下来 m 行，第 i 行三个整数表示 u_i、v_i、w_i。
接下来 k 行，第 i 行两个整数表示 l_i、r_i。
输出格式
一行一个整数，表示小 Y最早第多少秒能回到家中。
数据范围
测试点 1~3：k = 0。
测试点 4~6：n、m、k≤10^3。
测试点 1~10：2≤n≤10^5，1≤m≤2*10^5，0≤k≤10^5，1≤w_i≤10^4，0≤l_i＜r_i≤10^9，且保证输入的暴雨时间段互不相交、l_i 严格递增。
今日感想
我这图论大弱渣，寻找隐式图能力太差，总结：
我还要多刷题
……
所以我去刷题了
阿门