题目名称： Parade (游行) 题目编号： 未提供

题目描述： 在 JOI 王国，决定举办一场鼓号乐队游行来纪念 JOIG 的开幕。

在 JOI 王国中，有 N 座城市和 M 条单向街道，鼓号乐队需要从某个城市出发，经过多条街道返回该城市。游行的要求是：

• 从某个城市出发，经过一条或多条街道，最后回到该城市。
• 游行的街道长度总和必须等于 L。

由于王国的女王注意到，可能无法直接沿现有街道进行游行，因此决定允许逆向行驶部分街道。目标是最小化需要逆向行驶的街道数量。

给定 JOI 王国的城市和道路信息，判断是否能够通过反向一些道路的方向来举办游行。如果可以，输出最少需要反向的道路数；如果无法举办游行，则输出 -1。

输入： 第一行输入包含三个整数 N、M 和 L，分别表示城市数、道路数以及要求的街道长度总和。 接下来的 M 行每行包含三个整数 Ai、Bi 和 Ci，分别表示从城市 Ai 到城市 Bi 的一条单向街道，且该街道的长度为 Ci。

输出： 如果能够举办游行，输出最少需要反向的道路数。如果无法举办游行，则输出 -1。

约束条件：

• 2 ≦ N ≦ 1000
• 0 ≦ M ≦ 1000
• 1 ≦ L ≦ 1000000000
• 1 ≦ Ai ≦ N (1≦i≦M)
• 1 ≦ Bi ≦ N (1≦i≦M)
• Ai ≠ Bi (1≦i≦M)
• (Ai, Bi) ≠ (Aj, Bj) (1≦i < j≦M)
• 1 ≦ Ci ≦ 1000000 (1≦i≦M)

示例输入： 输入示例 1： 3 2 5 2 1 2 2 3 3

示例输出： 输出示例 1： 1 如果反向一条道路，就能举办游行，且最少需要反向的道路数是 1。

输入示例 2： 3 1 10 2 1 5

示例输出： 输出示例 2： -1 无法通过反向道路来达到目标游行总长度。

输入示例 3： 4 8 11 3 1 6 1 3 6 2 4 3 4 2 3 4 3 6 3 4 6 2 1 5 1 2 5

示例输出： 输出示例 3： 0 可以通过不反向任何道路来举办游行。

输入示例 4： 5 6 1000000000 5 2 1 2 3 1 3 4 1 4 2 1 2 1 1 1 3 1

示例输出： 输出示例 4： 1 需要反向一条道路来举办游行。

输入示例 5： 6 15 777777 1 3 497295 4 1 422722 4 5 607164 2 3 135688 5 2 995652 5 1 670296 3 1 138860 4 6 736614 6 3 620085 2 1 796353 6 4 949756 4 2 750680 6 5 591550 5 3 229431 3 2 668173

示例输出： 输出示例 5： 2 最少需要反向 2 条道路来举办游行。

题目算法分析： 这个问题可以看作是一个图论问题。我们需要找到从一个城市到同一个城市的路径（可能需要反向部分道路），并且路径的总长度恰好为 L。考虑到反向道路的最小数量，我们可以使用最短路径算法（例如 Dijkstra 算法）进行求解，同时考虑道路的反向操作。通过判断是否能够找到符合条件的路径，并更新最少反向道路数，可以得到答案。

使用的算法：

• 最短路径算法（Dijkstra 或 Bellman-Ford）用于寻找最短路径和反向操作。
• 贪心算法可能用于判断如何最小化反向的道路数。

版权信息： “Japan Olympiad in Informatics 1st Women's Division” by the Japan Committee for Informatics.