5092：最优路径
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 最优路径
## 题目描述
某城市的网络由 $N$ 个结点和 $M$ 条光纤组成，每条光纤连接两个不同的结点用于这两个结点**双向**传递信息。
每条光纤有如下两个属性：
- 成本： $F_i$ ，表示铺设该光纤的费用。
- 带宽： $S_i$ ，表示该光纤支持的数据传输速率。
现需要选择一条从编号为 $1$ 的结点到编号为 $N$ 的结点的路径，使得路径的**带宽与成本的比值**最大化。
对于一条从编号为 $1$ 的结点出发到编号为 $N$ 的结点结束的路径，该路径的带宽和成本的定义如下：
- 路径成本：路径上所有光纤的成本**之和**。
- 路径带宽：路径上所有光纤的**最小**带宽。
请编程计算出从编号为 $1$ 的结点出发，到编号为 $N$ 的结点结束，最优路径的带宽与成本的比值，并将结果乘以 $10^6$ 后向下取整输出。
## 输入格式
输入的第一行包含两个整数 $N$ 和 $M$ ，分别表示结点数量和光纤数量。
接下来的 $M$ 行，每行包含四个整数 $U_i$ 、 $V_i$ 、 $F_i$ 和 $S_i$ ，表示一条连接节点 $U_i$ 和 $V_i$ 的光纤，其成本为 $F_i$ ，带宽为 $S_i$ 。
## 输出格式
输出一个整数，表示最优路径的带宽与成本之比乘以 $10^6$ 后向下取整的结果。
## 样例
### 样例输入 1
```text
3 2
2 1 5 6
2 3 9 3
```
### 样例输出 1
```text
214285
```
### 样例输入 2
```text
4 4
1 2 5 8
2 4 8 9
1 3 9 4
3 4 2 9
```
### 样例输出 2
```text
615384
```
### 样例输入 3
```text
10 20
1 6 334 478
4 8 835 429
4 3 686 592
2 1 683 586
5 4 721 862
9 8 268 267
6 2 225 384
4 2 854 499
3 2 215 693
9 3 369 667
6 5 890 259
9 7 778 688
6 7 626 640
1 7 568 639
2 7 142 329
9 10 882 830
8 7 372 636
3 6 214 667
2 10 784 237
2 8 602 617
```
### 样例输出 3
```text
286804
```
## 说明/提示
样例 $1$ 说明
唯一的路径为 $1 \rightarrow 2 \rightarrow 3$ ：
- 路径带宽： $\min(6, 3) = 3$
- 路径成本： $5 + 9 = 14$
- 带宽与成本之比： $\frac{3}{14} \approx 0.214285$
- 乘以 $10^6$ 后向下取整： $214285$ 。
数据范围
对于 $10\%$ 的数据，满足图为链形，也就是说每个结点最多只有 $2$ 条与其连接的光纤。
对于 $40\%$ 的数据，满足 $1 \le N, M \leq 100$ 。
对于 $100\%$ 的数据，满足 $2 \leq N \leq 1000$ ， $1 \leq M \leq 1000$ ， $1 \leq F_i, S_i \leq 1000$ ， $1 \le U_i, V_i \le N$ ， $U_i \neq V_i$ 。
---
**题目来源：** 25年3月-C组（大咖）