{"problem":{"name":"[BCSP-X 2024 6 月初中组] 道路选择","description":{"content":"机器人警察得到了一张地图，记载了区内每一条道路的长度。 显然，为了减少犯罪行为被发现的可能性，犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线，他们希望得知任意两个地点之间，有多少条犯罪分子可能会选择的道路。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4176"},"statements":[{"statement_type":"Markdown","content":"机器人警察得到了一张地图，记载了区内每一条道路的长度。\n\n显然，为了减少犯罪行为被发现的可能性，犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线，他们希望得知任意两个地点之间，有多少条犯罪分子可能会选择的道路。\n\n## Input\n\n第一行，包含两个整数 $N, M$，表示区内的地点数和道路数。\n\n接下来 $M$ 行，每行包含三个整数 $x_i, y_i, l_i$，表示道路连接的两个不同地点的标号，以及道路的长度。道路是双向的。\n\n两个不同地点之间不会有超过一条道路。\n\n## Output\n\n输出一行，包含 $N(N - 1)\\div 2$ 个整数 $C_{1,2}, C_{1,3}, \\dots, C_{1,N}, C_{2,3}, C_{2,4}, \\dots, C_{2,N}, \\dots, C_{N-1,N}$。\n\n其中 $C_{x,y}$ 表示 $x$ 号地点到 $y$ 号地点之间有多少条犯罪分子可能会选择的道路。\n\n[samples]\n\n## Note\n\n### 数据范围\n\n- 对于分值为 $30$ 的子任务 $1$，保证 $N \\leq 50$；\n- 对于分值为 $30$ 的子任务 $2$，保证 $N \\leq 100$；\n- 对于分值为 $40$ 的子任务 $3$，保证 $N \\leq 500,1 \\leq l_i \\leq 200$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4176","tags":["搜索","2024","北京","最短路","BCSP-X"],"sample_group":[["5 6\n1 2 1\n2 3 1\n3 4 1\n4 1 1\n2 4 2\n4 5 4","1 4 1 2 1 5 6 1 2 1"]],"created_at":"2026-03-03 11:09:25"}}