题目描述
给定 nnn 个点， mmm 条边的无向图
每条边有一个花费和状态，状态为 000 表示该边处于锁定状态暂时不可通过， 111 表示可以通过
在节点 kkk 有一把钥匙，你取得钥匙后，便可以正常通过 000 状态边
现在你从 111 节点出发，需要求出到达节点 nnn 的最小花费
输入
第一行三个整数 n,m,kn, m, kn,m,k ，分别表示节点数，边数，钥匙所在节点
接下来 mmm 行，每行四个整数 ai,bi,ci,dia_i, b_i, c_i, d_iai,bi,ci,di ，表示 aia_iai 到 bib_ibi 之间存在一条无向边，通过该边花费 cic_ici ，其状态为 did_idi ， did_idi 取值仅为 000 或 111
输出
输出节点 11 到 nn 的最小花费，如果无法到达，输出 −1−1
样例输入 Copy
6 10 5
1 2 1 1
2 4 9 1
4 5 4 1
1 3 9 1
3 6 8 0
4 6 6 0
4 5 1 0
5 6 10 0
5 6 5 0
5 6 6 1
样例输出 Copy
19