[蓝桥杯青少年组省赛 2022] 路线

Luogu
IDLGB4292
Time1000ms
Memory512MB
DifficultyP2
图论2022图遍历蓝桥杯青少年组
有一个旅游景区,景区中有 $N$ 个景点,景点以数字 $1$ 到 $N$ 编号,其中编号为 $N$ 的景点为游客服务中心所在地。景区中有 $M$ 条连接路线,每条路线连接两个景点。 已知: 1. 一个景点可以被多条路线连接; 2. 景点之间的连接路线都可以双向行走; 当给出 $N$ 个景点和 $M$ 条连接路线,及 $M$ 条路线的连接关系,请你计算出从编号 $1$ 到编号 $N-1$ 的每一个景点,到达游客服务中心至少需要经过几条路线。如果某个景点不能到达游客服务中心则输出 $-1$。 例如: - 当 $N=5$,$M=4$ 时 - 4 条路线的连接关系为:$1\leftrightarrow2$、$1\leftrightarrow3$、$2\leftrightarrow4$、$2\leftrightarrow5$ - 则: - 景点 $1$ 到达景点 $5$(游客服务中心)至少经过 $2$ 条路线(路线 $1$,路线 $4$) - 景点 $2$ 到达景点 $5$ 至少经过 $1$ 条路线(路线 $4$) - 景点 $3$ 到达景点 $5$ 至少经过 $3$ 条路线(路线 $1$,路线 $2$,路线 $4$) - 景点 $4$ 到达景点 $5$ 至少经过 $2$ 条路线(路线 $3$,路线 $4$) ## Input 第一行输入两个正整数 $N$ 和 $M$($4 \leq N \leq 100$,$1 \leq M \leq 100$),$N$ 表示景点个数,$M$ 表示路线条数,两个正整数之间一个空格隔开。 接下来输入 $M$ 行,每行包括两个正整数 $S$,$E$($1 \leq S \leq N$,$1 \leq E \leq N$,$S \neq E$),两个正整数之间一个空格隔开,表示编号 $S$ 和编号 $E$ 的两个景点有一条路线连接。 ## Output 一行输出多个整数。按照 $1$ 到 $N-1$ 的编号顺序,分别输出每个景点到达编号 $N$(游客服务中心),至少经过几条路线可以到达,如果某个景点不能到达则输出 $-1$,整数之间一个空格隔开。 [samples]
Samples
Input #1
5 4
1 2
1 3
2 4
2 5
Output #1
2 1 3 2
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯青少年组省赛 2022] 路线",
    "description": {
      "content": "有一个旅游景区,景区中有 $N$ 个景点,景点以数字 $1$ 到 $N$ 编号,其中编号为 $N$ 的景点为游客服务中心所在地。景区中有 $M$ 条连接路线,每条路线连接两个景点。 已知: 1. 一个景点可以被多条路线连接; 2. 景点之间的连接路线都可以双向行走; 当给出 $N$ 个景点和 $M$ 条连接路线,及 $M$ 条路线的连接关系,请你计算出从编号 $1$ 到编号 $N-1$ 的每一",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4292"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个旅游景区,景区中有 $N$ 个景点,景点以数字 $1$ 到 $N$ 编号,其中编号为 $N$ 的景点为游客服务中心所在地。景区中有 $M$ 条连接路线,每条路线连接两个景点。\n\n已知:\n1. 一个景点可以被多条路线连接;\n2. 景点之间的连接路线都可以双向行走;\n\n当给出 $N$ 个景点和 $M$ 条连接路线,及 $M$ 条路线的连接关系,请你计算出从编号 $1$ 到编号 $N-1$ 的每一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments