#P17822. [Ontak2022]BIA

    ID: 16765 传统题 500~5000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>数据结构CF2500排序并查集ST表算法基础模拟

[Ontak2022]BIA

题目描述

有 nn 座山峰和 mm 条双向山路。第 ii 条山路连接 vi,uiv_i,u_i,难度为 wiw_i,类型为 cic_i:ci=0c_i=0 表示滑雪山路,ci=1c_i=1 表示射击山路。

一条训练路线从某个山峰 vv 出发,只沿射击山路到达另一个山峰 uu,然后只沿滑雪山路返回 vv,要求 u≠vu\ne v。

路线费用等于所用射击山路的最大难度,加上所用滑雪山路的最大难度。求最小费用,或判断不存在这样的路线。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行四个整数 vi,ui,wi,civ_i,u_i,w_i,c_i。

输出格式

输出最小费用;不存在合法路线则输出 -1。

数据范围

1≤n≤5000001\le n\le500000,0≤m≤10000000\le m\le1000000;1≤vi,ui≤n1\le v_i,u_i\le n,vi≠uiv_i\ne u_i;1≤wi≤1091\le w_i\le10^9;ci∈{0,1}c_i\in\{0,1\}。题面不保证无重边或图连通。

子任务

子任务 附加限制 分值
1 n≤500,m≤10000 7
2 n≤6000 13
3 n≤50000 29
4 所有滑雪山路难度为1 19
5 无额外限制 32

样例 1

输入:

6 8
5 2 4 1
1 3 2 1
2 6 2 0
4 3 10 1
4 1 3 1
6 3 4 0
4 5 1 0
6 4 5 1

输出:

9

样例 2

输入:

5 5
3 1 1 0
4 3 1 0
1 4 1 0
5 1 4 1
2 1 3 1

输出:

-1