← 返回题目列表

AtCoder · birthday0410_d

D. 老师和遗书

中文机器翻译题面 查看原题

問題文

我们在输出检查器中发现了一个缺陷,并将修复它。修改完成后我会立即重新判断! ! ! ! !对不起! ! ! ! ! ! !

重审已结束请原谅我,我会做任何事

私はちょうど他流試合でもする人のように K を注意して見ていたのです。私は、私の眼、私の心、私の身体、すべて私という名の付くものを五分の隙間もないように用意して、 K に向ったのです。罪のない K は穴だらけというよりむしろ明け放しと評するのが適当なくらいに無用心でした。私は彼自身の手から、彼の保管している要塞の地図を受け取って、彼の眼の前でゆっくりそれを眺める事ができたも同じでした。

K が理想と現実の間に彷徨してふらふらしているのを発見した私は、ただ一打で彼を倒す事ができるだろうという点にばかり眼を着けました。そうしてすぐ彼の虚に付け込んだのです。私は彼に向って急に厳粛な改まった態度を示し出しました。無論策略からですが、その態度に相応するくらいな緊張した気分もあったのですから、自分に滑稽だの羞恥だのを感ずる余裕はありませんでした。私はまず「精神的に向上心のないものは馬鹿だ」といい放ちました。これは二人で房州を旅行している際、 K が私に向って使った言葉です。私は彼の使った通りを、彼と同じような口調で、再び彼に投げ返したのです。しかし決して復讐ではありません。私は復讐以上に残酷な意味をもっていたという事を自白します。私はその一言で K の前に横たわる恋の行手を塞ごうとしたのです。

K は真宗寺に生れた男でした。しかし彼の傾向は中学時代から決して生家の宗旨に近いものではなかったのです。教義上の区別をよく知らない私が、こんな事をいう資格に乏しいのは承知していますが、私はただ男女に関係した点についてのみ、そう認めていたのです。 K は昔から精進という言葉が好きでした。私はその言葉の中に、禁欲という意味も籠っているのだろうと解釈していました。しかし後で実際を聞いて見ると、それよりもまだ厳重な意味が含まれているので、私は驚きました。道のためにはすべてを犠牲にすべきものだというのが彼の第一信条なのですから、摂欲や禁欲は無論、たとい欲を離れた恋そのものでも道の妨害になるのです。 K が自活生活をしている時分に、私はよく彼から彼の主張を聞かされたのでした。その頃からお嬢さんを思っていた私は、勢いどうしても彼に反対しなければならなかったのです。私が反対すると、彼はいつでも気の毒そうな顔をしました。そこには同情よりも侮蔑の方が余計に現われていました。

こういう過去を二人の間に通り抜けて来ているのですから、精神的に向上心のないものは馬鹿だという言葉は、 K に取って痛いに違いなかったのです。しかし前にもいった通り、私はこの一言で、彼が折角積み上げた過去を蹴散らしたつもりではありません。かえってそれを今まで通り積み重ねて行かせようとしたのです。それが道に達しようが、天に届こうが、私は構いません。私はただ K が急に生活の方向を転換して、私の利害と衝突するのを恐れたのです。要するに私の言葉は単なる利己心の発現でした。

「精神的に向上心のないものは、馬鹿だ」

私は二度同じ言葉を繰り返しました。そうして、その言葉が K の上にどう影響するかを見詰めていました。

「馬鹿だ」とやがて K が答えました。「僕は馬鹿だ」

K はぴたりとそこへ立ち留まったまま動きません。彼は地面の上を見詰めています。私は思わずぎょっとしました。私には K がその刹那に居直り強盗のごとく感ぜられたのです。しかしそれにしては彼の声がいかにも力に乏しいという事に気が付きました。私は彼の眼遣いを参考にしたかったのですが、彼は最後まで私の顔を見ないのです。そうして、徐々とまた歩き出しました。

(引自夏目漱石的《Kokoro》,JAPLJ强调)

K喜欢“精进”这个词,并且将路径看得高于一切......

哇...这是K-最短路径。无疑。这是什么……我明白了。


課題

两个整数 给出了 K, L 。50 一个简单的无向图,权重位于顶点下方,其中连接两点的路径之一是 K 最短的长度正好是 找到一个这样的 L 。

更详细地说,N 考虑一个带有加权顶点的简单无向图。该图的边必须连接两个不同的点,并且只能有一条边连接任意两点(不允许自环和多边)。此外,每条边必须具有正整数权重。该图的顶点 来自 1 当编号达到 N 时,顶点 1 到顶点 通往 N 的路线 应该是 K 最短的长度正好是 找到一个这样的 L 。

在路线中可以多次经过同一条边或多次访问同一顶点。而且,峰值不仅在末端,也在中间。 我们还考虑多次访问 N 的路线。当所有这样的路径按长度升序排列(这是它们经过的边的权重之和)时, 第 K 条路径的长度为 目的是制作 L 。


入力

K L

这是 K 最短路径的长度恰好是 表示查找满足 L 的图。

出力

N M
A_1 B_1 C_1
A_2 B_2 C_2
…
A_M B_M C_M

N 是图的顶点数,M 是表示图的边数的整数。 必须是1 \leq N \leq 50 。

继续 M 每条线代表一个边缘。 对于1 \leq i \leq M 反对 A_i, B_i, C_i 是顶点 A_i 和顶点 存在一条连接 B_i 的边,其权重为 C_i 。1 \leq A_i, B_i \leq N 和 满足 A_i \neq B_i 和 满足 1 \leq C_i \leq 10^9 。

输出图必须简单且顶点 导致 1 到顶点 通往 N 导致 K 第最短路径的长度恰好是 L 。

但是,如果没有这样的图,则仅输出-1。


制限

所有输入数据满足以下约束。

  • 1 \leq K \leq 5000
  • 1 \leq L \leq 10^9

採点基準

这个问题的输入数据可以分为三种类型:“正常情况”、“轻微严重情况”和“非常严重情况”。具体三类情况我就不透露了。本题的分值确定如下。

  • 如果您正确回答了所有“正常情况” 给出 1 点。
  • 除上述以外,如果您正确回答所有“轻微危险案件”问题,您还可以 3 点。
  • 除了上述之外,如果您正确回答了所有“相当严重的情况”问题,您还可以 196 点。

入力例1

3 8

出力例1

3 2
1 2 2
2 3 2

该图中的顶点 列出 3 条到 1 到顶点 通往 3 的最短路线。 长度至

  • 1 → 2 → 3 和长度 4 路线
  • 1 → 2 → 1 → 2 → 3 和长度 8 路线
  • 1 → 2 → 3 → 2 → 3 和长度 8 路线

变为。第二个和第三个数字具有相同的长度,但在这个问题中只有长度重要,所以哪个先出现并不重要。此外,可以多次通过同一条边,多次访问同一个顶点,或者 请注意,我们还考虑访问 3 的路线。


入力例2

5000 1

出力例2

-1

作者:JAPLJ
声明:夏目漱石,JAPLJ