yukicoder-1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/1 No.1 道のショートカット] ==

=== Description ===

{{{
#!html
<p>有$N$个城市，从$1$到$N$编号。有$V$条有向路径，第$i$条可以从$S_i$到$T_i$，需要花$Y_i$的钱，$M_i$单位的时间。</p>

<p>你从$1$出发要到$N$去，求不花超过$C$元钱的情况下的最短时间。如果不能到达，输出$-1$。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$<br>
$C$<br>
$V$<br>
$S_1$ $S_2$ $S_3$ $\dots$ $S_V$<br>
$T_1$ $T_2$ $T_3$ $\dots$ $T_V$<br>
$Y_1$ $Y_2$ $Y_3$ $\dots$ $Y_V$<br>
$M_1$ $M_2$ $M_3$ $\dots$ $M_V$<br>
</p>

<p>$2 \le N \le 50, 1 \le V \le 1500, 1 \le Y_i \le C \le 300, 1 \le S_i < T_i \le N, 1 \le M_i \le 1000$</p>
}}}

=== Output ===

{{{
#!html
<p>输出最短时间，不能到达的话输出$-1$。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3
100
3
1 2 1
2 3 3
10 90 10
10 10 50
</pre>
}}}
输出
{{{
#!html
<pre>
20
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
3
100
3
1 2 1
2 3 3
1 100 10
10 10 50
</pre>
}}}
输出
{{{
#!html
<pre>
50
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
10
10
19
1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9
3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10
8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6
8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4
</pre>
}}}
输出
{{{
#!html
<pre>
-1
</pre>
}}}

No.1 道のショートカット

Description

有$N$个城市，从$1$到$N$编号。有$V$条有向路径，第$i$条可以从$S_i$到$T_i$，需要花$Y_i$的钱，$M_i$单位的时间。

你从$1$出发要到$N$去，求不花超过$C$元钱的情况下的最短时间。如果不能到达，输出$-1$。

Input

$N$
$C$
$V$
$S_1$ $S_2$ $S_3$ $\dots$ $S_V$
$T_1$ $T_2$ $T_3$ $\dots$ $T_V$
$Y_1$ $Y_2$ $Y_3$ $\dots$ $Y_V$
$M_1$ $M_2$ $M_3$ $\dots$ $M_V$

$2 \le N \le 50, 1 \le V \le 1500, 1 \le Y_i \le C \le 300, 1 \le S_i < T_i \le N, 1 \le M_i \le 1000$

Output

输出最短时间，不能到达的话输出$-1$。

Sample

Sample 1

输入

310031 2 12 3 310 90 1010 10 50

输出

20

Sample 2

输入

310031 2 12 3 31 100 1010 10 50

输出

50

Sample 3

输入

1010191 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 93 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 108 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 68 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4

输出

-1