#P18670. Shuttle Tour
Shuttle Tour
Shuttle Tour
Prof.Chen 在 ICPC 区域赛中夺冠,取得了下一年 ICPC 世界总决赛的参赛资格。为了在即将到来的总决赛中取得好成绩,他和队友正在 Byteburg 参加 ICPC 决赛前训练营。
Byteburg 是一座美丽的城市,有 处景点,编号为 。景点之间有 条双向道路,任意两个地点都可以直接或间接到达。城中至多有 个地点恰好与一条道路相连。
遗憾的是,有些景点可能没有开放;也可能全部开放。每天完成五个小时的训练后,Prof.Chen 都会浏览旅游网站查看开放情况,并制定穿梭游览计划。你需要处理 个操作,操作有以下两种:
1 x:切换编号为 的景点的开放状态。如果原来开放,就将其关闭;如果原来关闭,就将其开放。2 l r:Prof.Chen 计划乘车游览编号在 内的每个开放景点。车辆可以从任意一个地点出发,沿道路行驶,最终返回出发地点,并使所有这些开放景点都至少被访问一次。**即使某个地点的景点关闭,车辆仍然可以到达或经过该地点。**出发地点和路线都由 Prof.Chen 自由选择,他希望路线的总长度最小。
请对每个第二类操作求出最短路线的长度。注意, 是原始景点编号的区间,途中也可以经过该区间之外的地点。
输入格式
第一行包含两个整数 ,满足 ,分别表示地点数量和操作数量。
第二行包含一个长度为 的字符串 ,每个字符为 0 或 1。 表示编号为 的景点初始关闭, 表示初始开放。
接下来的 行,每行包含三个整数 ,满足 、、,表示一条连接 和 、长度为 的双向道路。保证所有地点互相连通。
接下来的 行,每行按上述格式描述一个操作:
1 x中,。2 l r中,。
保证恰好与一条道路相连的地点不超过 个。
输出格式
对于每个第二类操作,输出一行整数,表示所需路线的最小总长度。
如果 内的景点全部关闭,输出 -1。如果其中只有一个景点开放,可以直接从该地点出发并停留,路线长度为 。
样例输入 1
5 6
10110
1 2 1
1 3 10
2 4 100
3 5 1000
2 1 5
1 3
2 1 5
2 2 4
2 5 5
2 1 1
样例输出 1
222
202
0
-1
0