比赛场次 519
比赛名称 EYOI与SBOI开学欢乐赛3rd
比赛状态 已结束比赛成绩
开始时间 2022-09-05 19:00:00
结束时间 2022-09-05 22:00:00
开放分组 全部用户
注释介绍 有思路的,细心点儿,争取多拿分;
没思路的,大胆点儿,争取拿到分;
题目名称 基础最短路练习题
输入输出 basiczdl.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarムラサメ AAAAAAAAAA 1.370 s 6.97 MiB 100

基础最短路练习题

★★   输入文件:basiczdl.in   输出文件:basiczdl.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

给定$n$个点$m$条边的简单无向连通图$G$,边有边权。保证没有重边和自环。

定义一条简单路径的权值为路径上所有边边权的异或和。

保证$G$中不存在简单环使得边权异或和不为$0$。

$Q$次询问$x$到$y$的最短简单路径。

【输入格式】

第一行三个正整数$n,m,Q$。

接下来$m$行,一行三个非负整数$x,y,v(1≤x,y≤n)$,表示一条连接$x,y$,权值为$v$的无向边。保证没有重边和自环。

接下来$Q$行,一行两个正整数$x,y(1≤x,y≤n)$,表示一次询问。

【输出格式】

$Q$行,一行一个整数表示答案。

【样例输入】

3 2 1
1 2 2
2 3 3
1 3

【样例输出】

1

【数据规模与约定】

对于$100\%$的数据,满足$1≤n≤10^5,1≤m≤2n,0≤v<2^{30}$。

【来源】

Luogu P5651