#P12604. 「FAOI-R6」魂灵之影
「FAOI-R6」魂灵之影
题目背景
此题因撞题已移出 FAOI Round 6.
Draw me to the light, let the curse be lifted
We can rise above the roar
With the bite of every devil
We've felled before
Drown them out
Let the fog give way to clarity
There is power in the strain of every drop I bleed
I am the venom and the cure
Take me
Through the fear, through the heart that's broken
Our world lies in wait for me
Every tear, every scar left open
This is the taming of the beast
I'll end this war you started
I'll stitch this wound with bloodshed
You are my wicked victory
https://music.163.com/#/song?id=2672191019
题目描述
给定一个无向连通图,边带权,可能存在重边自环。有 次查询,每次给定 ,求所有以 为起点, 为终点的路径(不要求为简单路径)中,边权和 的最小值是多少。
交互方式
本题为交互题,只支持 C++ 语言提交,并且不支持 C++14 (GCC 9)。
你需要编写以下三个函数:
void Ready(int T, int subtask_id)
该函数在每个测试点中仅会调用一次,两个参数表示该测试点的数据组数和子任务编号。样例的子任务编号为 。
void Set(int n, int m, int q, vector <int> u, vector <int> v, vector <int> w)
在调用 Ready
之后,该函数会(在每个测试点中)被调用 次,其中 分别表示图的边数和点数。 的大小均为 , 表示图的一条边。
int Go(int x, int y, int z)
每次调用 Set
之后,该函数会(在每组数据中)被调用 次,每次调用表示一次查询。返回值应为本次查询的答案。
你可以直接以下发文件中的 template.cpp
为基础编写。
输入格式
以下格式只对本地测试有效,但变量名的含义与实际评测相同。在实际评测中,请不要试图从标准输入(stdin)读取任何内容。
本题有多组数据。
第一行两个非负整数 和 ,分别表示数据组数和 Subtask 编号。
特别地,样例满足 。
对于每组数据:
- 第一行是空行。
- 第二行三个非负整数 。
- 接下来 行,每行三个非负整数 ,表示一条边。
- 接下来 行,每行三个正整数 ,表示一次查询。
输出格式
以下格式只对本地测试有效,但变量名的含义与实际评测相同。在实际评测中,请不要试图向标准输出(stdout)打印任何内容。
对于每组数据:
- 第一行是空行。
- 下面 行,每行一个非负整数,表示答案。
2 -1
2 1 1
1 2 1
1 2 2
3 3 1
1 2 1
2 3 1
1 3 1
1 3 2
1
0
提示
【样例解释】
对于第 组数据的唯一一组询问,所有路径均形如 ,可以证明所有路径的权值均为 。
对于第 组数据的唯一一组询问,路径 权值为 ,路径 的答案为 ,所以答案为 。
【数据范围】
对于 的数据,,,,,,,保证图连通。
请下载附件中的 judge_result.jpeg
以了解交互库所占用资源的规模。如果你不想下载附件的话,我们在这里用一句话概括一下:保证交互库的运行时间不超过 0.15 秒,占用的内存不超过 60 MB。
本题开启子任务捆绑测试。
- Subtask 0 - Subtask 4(10 pts):,。
- Subtask 0(2 pts):。
- Subtask 1(2 pts):。
- Subtask 2(1 pts):,。
- Subtask 3(4 pts):,,。
- Subtask 4(1 pts):在 Subtask 0 - Subtask 4 下无特殊限制。
- Subtask 5 - Subtask 9(90 pts):,,。
- Subtask 5(20 pts):。
- Subtask 6(20 pts):。
- Subtask 7(10 pts):。
- Subtask 8(10 pts):。
- Subtask 9(30 pts):在 Subtask 5 - Subtask 9 下无特殊限制。
Idea:ppip,Solution:喵仔牛奶,Code:ppip,Data:035966_L3