请注意：样例不一定正确（发现问题、知道解法必关）
星际旅行
题目描述
宇宙中有\(n\)个星系，每个星系\(i\)有能量值\(e_i\)。存在\(m\)条双向虫洞，连接\(u\)和\(v\)星系，使用虫洞\(u→v\)需消耗能量c，并获得\(d\)的能量补充（若当前能量不足\(c\)则无法使用）。求从\(S\)到\(T\)的最小初始能量\(E0\)，使得能够到达\(T\)且最终能量\(≥0\)。若无法到达，输出-1。
输入格式
第一行四个整数\(n\),\(m\),\(S\),\(T\)。
第二行\(n\)个整数，第\(i\)个为\(e_i\)。
接下来\(m\)行：每行四个整数\(u\),\(v\),\(c\),\(d\)。
输出格式
最小初始能量\(E0\)，或输出-1。
输入输出样例 #1
输入 #1
4 4 1 4
10 5 8 3
1 2 4 3
2 3 2 1
3 4 5 0
1 4 9 0
输出 #1
7
说明/提示
\(30\%\)数据：\(n ≤10\)，虫洞双向无环
\(60\%\)数据：\(n ≤50\)，\(e_i ≤10^4\)
\(100\%\)数据：\(1 \leq n ≤200\)，\(1 \leq m ≤5*10^4\)，\(1 \leq e_i ≤10^9\)，\(1 \leq c≤10^9\),\(1 \leq d≤10^9\)
澳门旅行
题目背景
\(Kevinrzy103874\)计划去澳门旅行，由于有太多景点了，\(Kevinrzy103874\)去不玩，所以请你帮忙规划行程。
澳门是一个不大不小的地区，但有着丰富的文化底蕴与景点。
题目描述
本题开启O2优化
本题按子任务给分
本题有多组测试数据
对于每组数据，给定三个整数\(N\) 、\(M\)和\(Q\)，表示\(N\)个地点以及\(Kevinrzy103874\)有\(M\)点体力，\(Q\)件坏事。
对于每个地点，先会输入一个\(op\)，代表类型。
- 当\(op=1\)时：该地点是景点，会输入两个数\(l\)和\(t\)，表示去该景点会增加\(l\)点知识并减少\(t\)点体力；
- 当\(op=2\)时：该地点是休息区，会输入一个数\(t\)，表示去该地点会恢复\(t\)点体力（最多回到\(M\)点）；
每行最后跟一个坐标\((x,y)\)表示该地点的坐标。
但是，怎么会一帆风顺呢，\(Kevinrzy103874\)有未卜先知的能力，预测到有\(Q\)件坏事，每一件坏事是在时间\(t\)位于\((x_i,y_i)\)发生的，每遇见一件坏事，知识会减去\(l\)。
而当你要从\((x_1,y_1)\)去到\((x_2,y_2)\)要走直线距离（欧几里得距离四舍五入），如下图：
2号链接
\(Kevinrzy103874\)会以每单位时间\(1\)个单位长度的速度行走，每走\(1\)单位长度会消耗\(1\)体力，时间是无穷的，但地点最多去\(1\)次，并且精力有限，\(Kevinrzy103874\)想知道在体力耗尽之前，体力未耗尽之前从任意点出发回到原点可以学到的最多知识。
输入格式
输出格式
输出\(T\)行，表示从任意点出发回到原点并体力未耗尽的知识最大值。
输入输出样例 #1
输入 #1
1
3 20 1
1 10 3 1 1
2 5 4 5
1 8 2 6 6
3 6 6
输出 #1
10
输入输出样例 #2
输入 #2
1
4 30 2
1 15 4 2 2
2 8 5 6
1 12 3 8 4
1 10 5 3 7
4 5 6
7 3 7
输出 #2
25
说明/提示
样例解释1
地点信息：
- 地点1：景点，知识 \(+10\)，体力 \(-3\)，坐标 \((1,1)\)
- 地点2：休息区，体力 \(+5\)，坐标 \((4,5)\)
- 地点3：景点，知识 \(+8\)，体力 \(-2\)，坐标 \((6,6)\)
- 坏事：时间 \(3\)，坐标 \((6,6)\)
距离计算（四舍五入）：
- 原点 \((0,0)\) 到 \((1,1)\)：\(\sqrt{1^2 + 1^2} = \sqrt{2} \approx 1.41 \rightarrow 1\)
- \((1,1)\) 到 \((4,5)\)：\(\sqrt{3^2 + 4^2} = 5 \rightarrow 5\)
- \((4,5)\) 到 \((6,6)\)：\(\sqrt{2^2 + 1^2} = \sqrt{5} \approx 2.24 \rightarrow 2\)
- \((6,6)\) 到原点：\(\sqrt{6^2 + 6^2} = \sqrt{72} \approx 8.49 \rightarrow 8\)
最优路径：原点 \(\rightarrow\) 地点1 \(\rightarrow\) 返回原点
- 去程：距离 \(1\) + 景点消耗 \(3\) = \(4\) 体力
- 返程：距离 \(1\) = \(1\) 体力
- 总消耗：\(5\) 体力 \(< 20\) 体力
- 获得知识：\(10\) 点
样例解释2
地点信息：
- 地点1：景点，知识 \(+15\)，体力 \(-4\)，坐标 \((2,2)\)
- 地点2：休息区，体力 \(+8\)，坐标 \((5,6)\)
- 地点3：景点，知识 \(+12\)，体力 \(-3\)，坐标 \((8,4)\)
- 地点4：景点，知识 \(+10\)，体力 \(-5\)，坐标 \((3,7)\)
- 坏事1：时间 \(4\)，坐标 \((5,6)\)
- 坏事2：时间 \(7\)，坐标 \((3,7)\)
最优路径：原点 \(\rightarrow\) 地点1 \(\rightarrow\) 地点2 \(\rightarrow\) 地点3 \(\rightarrow\) 返回原点
距离计算：
- 原点 \(\rightarrow\) \((2,2)\)：\(\sqrt{2^2 + 2^2} = \sqrt{8} \approx 2.83 \rightarrow 3\)
- \((2,2)\) \(\rightarrow\) \((5,6)\)：\(\sqrt{3^2 + 4^2} = 5 \rightarrow 5\)
- \((5,6)\) \(\rightarrow\) \((8,4)\)：\(\sqrt{3^2 + 2^2} = \sqrt{13} \approx 3.61 \rightarrow 4\)
- \((8,4)\) \(\rightarrow\) 原点：\(\sqrt{8^2 + 4^2} = \sqrt{80} \approx 8.94 \rightarrow 9\)
体力消耗计算：
- 移动消耗：\(3 + 5 + 4 + 9 = 21\) 体力
- 景点消耗：\(4 + 3 = 7\) 体力
- 休息恢复：\(+8\) 体力
- 净消耗：\(21 + 7 - 8 = 20\) 体力 \(< 30\) 体力
知识获取： \(15 + 12 = 27\) 点
坏事规避： 合理安排时间，避开坏事发生
最终输出25： 在最优路径规划中，为避免坏事损失部分知识，最终获得 \(25\) 点知识。
数据范围与约定
对于\(100 \%\)的数据，保证
\(1 \leq T \leq 10\)
\(1 \leq N,Q \leq 3 \times 10^5\)
\(-10^{18} \leq l,t,M \leq 10^{18}\)
\(-10^{9} \leq x,y,x_i,y_i \leq 10^{9}\)
这么难的题，肯定有子任务啊！
| \(Subtask1,6\)(10point) | \(T = 1\) | \(1 \leq N,Q \leq 10\) | \(-10 \leq l,t,M \leq 10\) | \(-10^{2} \leq x,y,x_i,y_i \leq 10^{2}\) |
|---|---|---|---|---|
| \(Subtask2,7\)(10point) | \(T=1\) | \(1 \leq N,Q \leq 10\) | \(-10^{3} \leq l,t,M \leq 10^{3}\) | \(-10^{4} \leq x,y,x_i,y_i \leq 10^{4}\) |
| \(Subtask3,8\)(20point) | \(T=1\) | \(1 \leq N,Q \leq 10^3\) | \(-10^{5} \leq l,t,M \leq 10^{5}\) | \(-10^{5} \leq x,y,x_i,y_i \leq 10^{5}\) |
| \(Subtask4,9\)(20point) | \(T \leq 5\) | \(1 \leq N,Q \leq 10^3\) | \(-10^{6} \leq l,t,M \leq 10^{6}\) | \(-10^{5} \leq x,y,x_i,y_i \leq 10^{5}\) |