G. Shortest Path Problem?

Codeforces

IDCF845G

Time3000ms

Memory512MB

Difficulty—

dfs and similargraphsmath

English · Original

Chinese · Translation

Formal · Original

You are given an undirected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times). You have to find the minimum length of path between vertex 1 and vertex _n_. **Note that graph can contain multiple edges and loops. It is guaranteed that the graph is connected.** ## Input The first line contains two numbers _n_ and _m_ (1 ≤ _n_ ≤ 100000, _n_ - 1 ≤ _m_ ≤ 100000) — the number of vertices and the number of edges, respectively. Then _m_ lines follow, each line containing three integer numbers _x_, _y_ and _w_ (1 ≤ _x_, _y_ ≤ _n_, 0 ≤ _w_ ≤ 108). These numbers denote an edge that connects vertices _x_ and _y_ and has weight _w_. ## Output Print one number — the minimum length of path between vertices 1 and _n_. [samples]

你被给定一个带权无向图。两点间某条路径的长度定义为该路径上所有边权的异或和（若某条边被经过多次，则在异或和中被包含相同次数）。你需要找到顶点 #cf_span[1] 与顶点 #cf_span[n] 之间的最短路径长度。 *注意：图中可能包含重边和自环。保证图是连通的。* 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[n - 1 ≤ m ≤ 100000]），分别表示顶点数和边数。接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[w]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[0 ≤ w ≤ 10^8]），表示一条连接顶点 #cf_span[x] 和 #cf_span[y] 且权值为 #cf_span[w] 的边。输出一个整数——顶点 #cf_span[1] 与顶点 #cf_span[n] 之间的最短路径长度。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[n - 1 ≤ m ≤ 100000]），分别表示顶点数和边数。接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[w]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[0 ≤ w ≤ 10^8]），表示一条连接顶点 #cf_span[x] 和 #cf_span[y] 且权值为 #cf_span[w] 的边。 ## Output 输出一个整数——顶点 #cf_span[1] 与顶点 #cf_span[n] 之间的最短路径长度。 [samples]

**Definitions** Let $ G = (V, E) $ be an undirected graph with: - $ V = \{1, 2, \dots, n\} $: set of vertices, - $ E \subseteq V \times V \times \mathbb{Z}_{\geq 0} $: set of weighted edges, where each edge $ (x, y, w) $ connects vertices $ x $ and $ y $ with weight $ w \in [0, 10^8] $. Let $ \oplus $ denote bitwise XOR. For a path $ P $ from vertex $ u $ to vertex $ v $, define its *length* as the XOR of weights of all edges in $ P $, counting multiplicity (i.e., if an edge is traversed $ k $ times, its weight is XORed $ k $ times). **Constraints** 1. $ 1 \leq n \leq 10^5 $, $ n-1 \leq m \leq 10^5 $ 2. $ 1 \leq x, y \leq n $, $ 0 \leq w \leq 10^8 $ for each edge $ (x, y, w) $ 3. $ G $ is connected and may contain multiple edges and self-loops. **Objective** Find the minimum XOR path length between vertex $ 1 $ and vertex $ n $: $$ \min_{P \in \mathcal{P}_{1,n}} \left( \bigoplus_{e \in P} w(e) \right) $$ where $ \mathcal{P}_{1,n} $ is the set of all paths (with possible edge repetitions) from vertex $ 1 $ to vertex $ n $.

Samples

Input #1

Output #1

Input #2

2 2
1 1 3
1 2 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. Shortest Path Problem?",
    "description": {
      "content": "You are given an undirected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF845G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个带权无向图。两点间某条路径的长度定义为该路径上所有边权的异或和（若某条边被经过多次，则在异或和中被包含相同次数）。你需要找到顶点 #cf_span[1] 与顶点 #cf_span[n] 之间的最短路径长度。\n\n*注意：图中可能包含重边和自环。保证图是连通的。*\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100000]，#...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices,  \n- $ E \\subseteq V \\times V \\times \\mathbb{Z}_{\\geq 0} $: set of weighted edges, whe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments