[BCSP-X 2024 6 月初中组] 道路选择

Luogu

IDLGB4176

Time5000ms

Memory256MB

DifficultyP4

搜索2024北京最短路BCSP-X

机器人警察得到了一张地图，记载了区内每一条道路的长度。显然，为了减少犯罪行为被发现的可能性，犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线，他们希望得知任意两个地点之间，有多少条犯罪分子可能会选择的道路。 ## Input 第一行，包含两个整数 $N, M$，表示区内的地点数和道路数。接下来 $M$ 行，每行包含三个整数 $x_i, y_i, l_i$，表示道路连接的两个不同地点的标号，以及道路的长度。道路是双向的。两个不同地点之间不会有超过一条道路。 ## Output 输出一行，包含 $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}$。其中 $C_{x,y}$ 表示 $x$ 号地点到 $y$ 号地点之间有多少条犯罪分子可能会选择的道路。 [samples] ## Note ### 数据范围 - 对于分值为 $30$ 的子任务 $1$，保证 $N \leq 50$； - 对于分值为 $30$ 的子任务 $2$，保证 $N \leq 100$； - 对于分值为 $40$ 的子任务 $3$，保证 $N \leq 500,1 \leq l_i \leq 200$。

Samples

Input #1

Output #1

1 4 1 2 1 5 6 1 2 1

API Response (JSON)

{
  "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$，表...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments