AT_pakencamp_2021_day3_h パ研王国と貨物輸送

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_h パ研王国は $ 1 $ から $ N $ までの番号が振られた $ N $ 個の都市と、それらの都市間を結ぶ $ M $ 本の道路からなります。$ i $ 本目の道路は、都市 $ u_i $ と都市 $ v_i $ を双方向に結んでおり、その長さは $ l_i $ メートルです。 あなたの属するペンギン株式会社は、パ研王国内において貨物の輸送を行うという仕事を $ K $ 個受注しました。$ i $ 番目の仕事（仕事 $ i $ とする）では、都市 $ s_i $ にある貨物を都市 $ g_i $ に移動させる必要があり、仕事に成功した場合 $ m_i $ 円の利益が生まれます。 ただしこの $ K $ 個の仕事には時間制限があり、ある時刻 $ T $ までに仕事を行うことができなかった場合得られる利益は $ 0 $ 円になります。 あなたは、ペンギン株式会社の利益のため、以下のような輸送計画を立てることにしました。 1. まずはじめに、行う仕事の集合を決める。 2. その後、行う仕事それぞれについて（仕事 $ x $ とする）、経由する都市の列 $ (a_0=s_x,\ a_1,\ \ldots,\ a_k=g_x) $、および仕事を開始する時刻 $ t $ を決める。$ t $ は整数である必要があり、また、このとき $ 1\ \leq\ i\ \leq\ k $ について都市 $ a_{i-1} $ と都市 $ a_i $ は直接道路で結ばれている必要がある。 3. 時刻 $ 0 $ 以降、2. までで決めた内容をもとに実際に仕事を行う。行う仕事それぞれについて、時刻 $ t $ に輸送する貨物を会社の車に乗せた状態から仕事を開始する。その後はその仕事が完了するまでの間、分速 $ 1 $ メートルの速さで今いる地点から次に経由する都市に向けて移動し続ける。途中で車が止まることはない。 **パ研王国の道路は非常に狭いため、同じ時刻に同じ道路内の同じ地点（道路の両端を除く）に複数の車が存在することは許されません。** 得られる利益の合計をできるだけ大きくしてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ T $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ $ \hspace{0.8cm}\vdots $ $ u_M $ $ v_M $ $ l_M $ $ s_1 $ $ g_1 $ $ m_1 $ $ s_2 $ $ g_2 $ $ m_2 $ $ \hspace{0.8cm}\vdots $ $ s_K $ $ g_K $ $ m_K $

あなたの輸送計画の内容を、以下の形式に従って出力せよ。 > $ P $ $ \text{data}_1 $ $ \text{data}_2 $ $ \hspace{0.3cm}\vdots $ $ \text{data}_P $ まず、$ P $ はあなたの輸送計画において行われる仕事の数である。この値は $ 0 $ 以上 $ K $ 以下である必要がある。 そして、その後に出力される $ \text{data}_i $ はあなたの輸送計画において行われる仕事のうち、$ i $ 個目のものについての情報を表す。この情報は、以下の形式で出力される必要がある。 > $ x $ $ t $ $ k $ $ a_0 $ $ a_1 $ $ \ldots $ $ a_k $ まず、$ x $ は $ \text{data}_i $ において行われる仕事が仕事 $ x $ であることを表す。$ \text{data}_1 $ における $ x $、$ \text{data}_2 $ における $ x $、$ \cdots $、$ \text{data}_P $ における $ x $ は互いに異なる必要がある。 次に、$ t $ は仕事 $ x $ を開始する時刻が $ t $ であることを表す。この値は $ 0 $ 以上 $ T $ 以下である必要があり、また $ t $ から始めて経由する都市を順に訪れていったとき、最後の頂点に到着する時刻が $ T $ より真に遅くなってはならない。 そして最後に、$ k $ および数列 $ a=(a_0,a_1,\ldots,a_k) $ は、経由する都市の列を表す。$ a $ の各要素は互いに異なる必要があることに注意せよ。

### 制約 - $ N=100 $ - $ M=200 $ - $ K=500 $ - $ T=10000 $ - $ 1\ \leq\ u_i\ \lt\ v_i\ \leq\ N $ - $ 1\ \leq\ l_i\ \leq\ 100 $ - $ (u_i,v_i)\ \neq\ (u_j,v_j) $ - $ 1\ \leq\ s_i,t_i\ \leq\ N $ - $ s_i\ \neq\ t_i $ - $ 1\ \leq\ m_i\ \leq\ 1000 $ - 入力はすべて整数である - どの都市からどの都市へも、いくつかの道路を経由して移動することができる。 ### テストケースの生成方法 テストケースは全部で $ 20 $ 個あり、それらは制約を満たす範囲内でほぼランダムに生成されています。 具体的には、[こちら](https://img.atcoder.jp/pakencamp-2021-day3/bf6dee05788c2762cbe1d62d26cac87a.zip)の生成コードによって生成されています。 ### 採点 $ 20 $ 個のテストケースのうちのいずれかで問題文中の条件（同じ時刻に同じ道路内の同じ地点に複数の車が存在してはいけない）に反する出力、ないし不正な出力がなされた場合、あなたの提出は不正解となり、得られる得点は $ 0 $ となる。 そうでなく、あなたが $ 20 $ 個のテストケースすべてにおいて正当な出力をした場合、あなたの得点は $ 20 $ 個のテストケースすべてにおける利益の合計を $ S $ として、$ \min(800,\frac{S}{10000}) $ の小数点以下切り上げとなる。 ### Sample Explanation 1 これは説明用の入力例であり、制約を満たしていないことに注意してください。 この例では、得られる利益は $ 11 $ 円となります。 原案: \[define\](https://atcoder.jp/users/penguinman)