TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1731
  • Problem
  • P1731异或最短路 | 进入2012NOIP复赛的选手名单
    Limits : Time Limit : 10000 MS   Memory Limit : 262144 KB
    Judgment Tips : 1s,256MB
    Description

    一个 \(n\) 个节点 \(m\) 条边的无向图,可能有重边和自环,但保证连通。一条路径的代价为路径上所有边的权值的异或和,\(q\) 次询问两点间的最短路。


    汪博
    邓睿凡
    刘人榕
    邵年
    罗怡
    王乾
    胡健
    刘东立
    汤佳懿
    刘宸嘉
    罗一风
    张智浩
    高翰林
    李兆童
    周都
    简英伦
    丁湛钊
    蒋松儒
    王裕栋
    蒋书宁
    张嘉昕
    赵楚渝
    王薪焱
    胡江海
    程也

    名单上的同学如果初赛前没在www.noi.cn注册,请在周一前到www.noi.cn补注册!

    Input Format

    第一行两个整数 \(n,m\)

    接下来 \(m\) 行,每行三个整数 \(x,y,z\) ,表示一条连接 \(x,y\) 的无向边,权值为 \(z\)

    接下来一行一个整数 \(q\)

    接下来 \(q\) 行,每行两个整数 \(x,y\) ,一次询问的起点和终点。

    Output Format

    输出 \(q\) 行,每行一个整数,表示最短路。

    Sample Input 1

    3 3
    1 2 3
    1 3 2
    3 2 0
    3
    1 2
    1 3
    2 3

    Sample Output 1

    2
    2
    0

    Sample Input 2

    2 2
    1 1 3
    1 2 3
    1
    1 2

    Sample Output 2

    0

    Hint

    \(n,m,q\leq 10^5\)
    $1\leq x,y\leq n$
    $0\leq z\lt 2^{60}$


    Source  CF845G加强版 nodgd提供数据