[图论与代数结构 201] 最短路问题_1

Luogu
IDLGB3601
Time1000ms
Memory512MB
DifficultyP3
图论最短路
给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。 **注意，图可能存在重边和自环，保证不存在负环。** ## Input 第一行两个整数 $n, m$。 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$。表示一条从 $u_i$ 到 $v_i$ 长度为 $w_i$ 的有向边。 ## Output 一行 $n$ 个整数，第 $i$ 个整数表示 $1$ 到 $i$ 的最短路径长度，如果不存在从 $1$ 到 $i$ 的路径则第 $i$ 个整数用 $-1$ 替代。 [samples] ## Note 本题没有部分分。 对于所有数据，$1\leq n,m \leq 2\times 10^3$，$-10^9\leq w_i\leq 10^9$。 请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。
Samples
Input #1
4 5
1 2 1
2 3 4
1 3 3
4 1 5
3 1 2
Output #1
0 1 3 -1
Input #2
10 50
5 9 6
1 3 10
3 1 1
10 2 5
8 5 1
10 10 6
6 5 2
1 5 10
2 5 5
10 1 4
1 5 2
8 8 7
7 2 7
9 2 8
3 1 4
6 2 5
3 9 9
4 9 5
5 10 9
10 1 9
5 4 5
9 1 2
5 10 6
3 8 7
10 3 7
5 8 8
9 2 6
9 8 6
3 2 8
1 3 8
1 10 1
7 8 4
9 4 5
4 6 2
2 7 6
10 1 5
9 9 7
6 7 4
1 1 7
8 3 10
8 3 9
10 9 8
3 9 1
7 4 8
1 5 4
8 4 4
3 4 4
9 9 2
2 10 4
8 9 6
Output #2
0 6 8 7 2 9 12 10 8 1
API Response (JSON) 
{
  "problem": {
    "name": "[图论与代数结构 201] 最短路问题_1",
    "description": {
      "content": "给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。 **注意，图可能存在重边和自环，保证不存在负环。**",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3601"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。\n\n**注意，图可能存在重边和自环，保证不存在负环。**\n\n## Input\n\n第一行两个整数 $n, m$。\n\n接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$。表示一条从 $u_i$ 到 $v_i$ 长度为 $w_i$ 的有向边。\n\n## Output\n\n一行 $n$ 个整数，第 $i$ 个整...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac