コミュニティアイコン プチコン 非公式コミュニティ トピック

アバター
こういち ◆.Id/aHiU36hu
2020/7/11 13:34
コンテスト
問題(Alchemy1)
魔女のモカ・メルカさんは錬金術で、物質0を物質1に変えてやろうと思い立ちました。
物質は(0,1を含めて)N個あり、物質を変化させるためのレシピがM個あります。

物質の変化には、魔法石を1つ消費する変化と、魔法石を消費しない変化があり、i番目のレシピには、物質F_iから物質T_iに変化させるための方法と、魔法石消費する個数Bが載っています。
モカさんは、出来るだけ消費する魔法石を少なくしたいです。
消費する魔法石の個数と、その個数で物質を変化させるために経由する物質を順番に答えなさい。
ただし、物質0から物質1まで変化させるような手順が必ず1つは存在するものとします。
また、答えが複数ある場合、どのような手順を選んでも良いものとします。

コメント

アバター
こういち 2020/7/11 13:35 ◆.Id/aHiU36hu
入力は以下の形式で与えられます。
N,M
F_0,T_0,B_0
F_1,T_1,B_1

F_(M-1),T_(M-1),B_(M-1)

制約
1<N<M<=10000
F_i≠T_i
0<=F_i,T_i<N
0<=B<=1
入力は全て整数で与えられます。
アバター
こういち 2020/7/11 13:40 ◆.Id/aHiU36hu
スーさんのオリキャラをお借りしました。(許可はとってあります)

次回予告:難易度上がります。
アバター
SatoshiMcCloud 2020/7/15 17:44 ◆Z1qfV11i63Jr
(興味あるけど、なかなか手が回らないのが心苦しい)
アバター
こういち 2020/7/15 23:20 ◆.Id/aHiU36hu
SatoshiMcCloudさん
正直、プチコンと相性が良くない問題だとは思うので、無理して解く必要はないと思います。(ただ、わりと使い道があるので、解けてほしい問題ではある)
アバター
こういち 2020/7/16 21:35 ◆.Id/aHiU36hu
どうでもいいけど、この問題。モカさん==錬金術とも取れてしまうな…
アバター
こういち 2020/8/2 15:52 ◆.Id/aHiU36hu
http://petitverse.hosiken.jp:80/community/petitcom/topic/?read=1541&ukey=0
新たな問題を投稿しました。
解説はしばしお待ちを。経路を探索するパートと解を復元するパートに分けて解説する予定。

コメントを書く

  • こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
  • プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
  • こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
  • ユーザー登録なしで書き込みができます
  • 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
  • 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
  • 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります

- WEB PATIO -