{"problem":{"name":"[图论与代数结构 202] 最短路问题_2","description":{"content":"给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。 **注意，图可能存在重边和自环。**","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3602"},"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$ 个整数表示 $1$ 到 $i$ 的最短路径长度，如果不存在从 $1$ 到 $i$ 的路径则第 $i$ 个整数用 $-1$ 替代。\n\n[samples]\n\n## Note\n\n本题没有部分分。\n\n对于所有数据，$1\\leq n,m \\leq 3\\times 10^5$，$1\\leq w_i\\leq 10^9$。\n\n请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3602","tags":["图论","最短路"],"sample_group":[["4 5\n1 2 1\n2 3 4\n1 3 3\n4 1 5\n3 1 2\n","0 1 3 -1"],["10 50\n5 9 6\n1 3 10\n3 1 1\n10 2 5\n8 5 1\n10 10 6\n6 5 2\n1 5 10\n2 5 5\n10 1 4\n1 5 2\n8 8 7\n7 2 7\n9 2 8\n3 1 4\n6 2 5\n3 9 9\n4 9 5\n5 10 9\n10 1 9\n5 4 5\n9 1 2\n5 10 6\n3 8 7\n10 3 7\n5 8 8\n9 2 6\n9 8 6\n3 2 8\n1 3 8\n1 10 1\n7 8 4\n9 4 5\n4 6 2\n2 7 6\n10 1 5\n9 9 7\n6 7 4\n1 1 7\n8 3 10\n8 3 9\n10 9 8\n3 9 1\n7 4 8\n1 5 4\n8 4 4\n3 4 4\n9 9 2\n2 10 4\n8 9 6\n","0 6 8 7 2 9 12 10 8 1"]],"created_at":"2026-03-03 11:09:25"}}