{"problem":{"name":"[JOI Open 2022] 放学路 / School Road","description":{"content":"河狸国由 $N$ 座城市组成，编号为 $1 \\sim N$。共有 $M$ 条道路连接这些城市，道路编号为 $1 \\sim M$。道路 $i$（$1 \\le i \\le M$）双向连接城市 $A_i$ 和 $B_i$，并且道路 $i$ 的长度为 $C_i$。保证经过一定数量的道路，均可以从任意一座城市到达任意其他城市。 Bitaro 是一只住在城市 $1$ 的河狸。他要去城市 $N$ 上学。他上学","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1122304},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8426"},"statements":[{"statement_type":"Markdown","content":"河狸国由 $N$ 座城市组成，编号为 $1 \\sim N$。共有 $M$ 条道路连接这些城市，道路编号为 $1 \\sim M$。道路 $i$（$1 \\le i \\le M$）双向连接城市 $A_i$ 和 $B_i$，并且道路 $i$ 的长度为 $C_i$。保证经过一定数量的道路，均可以从任意一座城市到达任意其他城市。\n\nBitaro 是一只住在城市 $1$ 的河狸。他要去城市 $N$ 上学。他上学通常都走一样的路线。他的上学路线满足如下条件。\n\n- 令 $L$ 为从城市 $1$ 到城市 $N$ 的最短距离。\n- Bitaro 的上学路是一条连接城市 $1$ 和城市 $N$ 且长度为 $L$ 的路径。\n\n因为今天天气好，Bitaro 决定绕路回家。也就是说，他会选择一条从城市 $N$ 到城市 $1$ 且长度大于 $L$ 的路径。因为 Bitaro 很容易厌倦，他不想经过同一座城市多于一次。因此，当他绕远路回家时，不允许经过同一座城市多于一次，并且不允许走回头路。\n\n给定河狸国的城市和道路的信息，写一个程序确定是否存在一条从学校到 Bitaro 的家的远路。\n\n**赛时提醒：Bitaro 不允许在回家途中经过相同的城市超过一次，但是并不禁止经过在他上学路线中经过的城市。**\n\n## Input\n\n第一行，两个正整数 $N, M$。\n\n接下来 $M$ 行，第 $i$ 行三个正整数 $A_i, B_i, C_i$。\n\n## Output\n\n输出一行，一个数。如果存在一条到 Bitaro 家的，长度大于 $L$ 且不经过同一座城市多于一次的路径，输出 $1$，否则输出 $0$。\n\n[samples]\n\n## Background\n\n**译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T3. [通学路](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement.pdf) / [School Road](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement-en.pdf)。**\n\n----\n\n在洛谷上，本题测试点和子任务配置可能导致评测结果页面难以理解。具体地，将评测结果页面中的子任务编号 $x$ 转为二进制后，从低到高第 $i$ 位为 $1$ 就表示子任务内所有测试点均满足题目中的子任务 $i$ 的限制。\n\n## Note\n\n**【样例解释 \\#1】**\n\n在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。\n\n有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。\n\n- 按顺序经过道路 $3 \\to 1$，长度为 $5$ 的路径，按 $4 \\to 2 \\to 1$ 的顺序经过城市。\n- 按顺序经过道路 $4 \\to 2$，长度为 $5$ 的路径，按 $4 \\to 3 \\to 1$ 的顺序经过城市。\n\n因为不存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $0$。\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#2】**\n\n在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。\n\n有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。\n\n- 按顺序经过道路 $3 \\to 1$，长度为 $5$ 的路径，按 $4 \\to 2 \\to 1$ 的顺序经过城市。\n- 按顺序经过道路 $4 \\to 2$，长度为 $6$ 的路径，按 $4 \\to 3 \\to 1$ 的顺序经过城市。\n\n因为存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $1$。\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#3】**\n\n这组样例满足子任务 1、2、3、5 的限制。\n\n----\n\n**【样例解释 \\#4】**\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#5】**\n\n这组样例满足子任务 1、2、3、5 的限制。\n\n----\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n- 子任务 1（7 分）：$M \\le 40$。\n- 子任务 2（15 分）：$N \\le 18$。\n- 子任务 3（23 分）：$M - N \\le 13$。\n- 子任务 4（35 分）：对于任意三座不同的城市 $a, b, c$，均存在一条从城市 $a$ 到城市 $c$ 且不经过城市 $b$ 的路径。\n- 子任务 5（20 分）：无特殊限制。\n\n对于所有数据，满足 $2 \\le N \\le {10}^5$，$1 \\le M \\le 2 \\times {10}^5$，$1 \\le A_i < B_i \\le N$，$1 \\le C_i \\le {10}^9$，保证经过一定数量的道路，均可以从任意一个城市到达任意其他城市。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8426","tags":["2022","O2优化","JOI（日本）"],"sample_group":[["4 4\n1 2 1\n1 3 2\n2 4 4\n3 4 3\n","0\n"],["4 4\n1 2 1\n1 3 3\n2 4 4\n3 4 3\n","1\n"],["3 4\n1 2 1\n1 2 2\n1 3 3\n1 3 3\n","0\n"],["4 5\n1 2 1\n1 3 2\n2 4 4\n3 4 3\n2 3 1\n","1\n"],["12 17\n2 4 656247308\n4 6 106088453\n1 5 754343261\n9 12 497827261\n3 8 759830309\n3 4 61084725\n1 6 324702188\n3 6 415317430\n7 12 846175092\n5 8 278621369\n1 10 891247646\n10 12 755236904\n6 8 511967203\n5 6 597197970\n1 7 800309458\n7 9 348347831\n10 11 134217757\n","0\n"]],"created_at":"2026-03-03 11:09:25"}}