本题属于 最短路 题，但较模板题还是有很大区别的。

我们可以视一条管道为一条边，然后对于每一条边保存连接的端点 $u,v$ 以及管道的花费 $c$ 和管道的流量 $f$。

本文中将 $c$ 的含义视为一条边的权值或两点之间的距离。

若视 Farmer John 的整个管道网络为一个图，则样例所表示的图如下：

题目让我们求出从 $1$ 到 $n$ 中，$\dfrac{\min\{f_i\}}{\sum c_i}$ 的最大值。

从上图来看，我们只能选择 $1 \to 2 \to 3$ 的路径。这样，最大值为 $\dfrac{\min(4,3)}{2+5}=\dfrac{3}{7}$。所以输出为 $\lfloor 10^6 \times \dfrac{3}{7} \rfloor=428571$。

我们不妨在样例的基础上增加一条边：

附加新输入：

3 3
2 1 2 4
2 3 5 3
1 3 3 6

则我们应当考虑路径 $1 \to 2 \to 3$ 和 $1 \to 3$。刚才已经分析了 $1 \to 2 \to 3$ 路径的答案，即 $\dfrac{3}{7}$。而 $1 \to 3$ 路径的答案为 $\dfrac{\min(6)}{3}=2$。由于 $2 \gt \dfrac{3}{7}$，所以 $2$ 比 $\dfrac{3}{7}$ 更优，输出 $\lfloor 10^6 \times 2 \rfloor=200000$。

$\text{Solution 1: 枚举}$

由于每个端点的 $f$ 都有可能成为所有的 $f$ 值的最小值，因而我们可对哪一条边的 $f$ 满足 $f=\min\{f_i\}$ 进行枚举。

保证 $\min\{f_i\}$ 后，再找最小的 ${\sum c_i}$ 即可，这样需要跑 $m$ 次 $\text{Dijkstra}$。

时间复杂度：$\mathcal O(m(n+m) \log n)$

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,head[1001],dis[1001],F[1001]; // 记录所有边的 f 值
double ans; // 保存最优解的值
bool vis[1001];
struct edge
{
    int nxt,to,w,f;
}e[2001];
struct node
{
    int pos,dis;
    bool operator<(const node &x)const // 从小到大为优先队列默认排序方式
    {
        return dis>x.dis;
    }
    // 重载运算符，把 dis 小的放在前面，但由于 priority_queue 的性质，需要颠倒过来
};
void add(int u,int v,int w,int f) // 链式前向星存边
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w; // 这里用 w 代替 c，符合常规习惯
    e[cnt].f=f;
    head[u]=cnt;
}
int dijkstra(int s,int minf)
{
    memset(dis,0x3f,sizeof(dis)); // 重置所有点到 1 的总距离（即所有 c 值总和）为 0x3f3f3f3f
    memset(vis,false,sizeof(vis)); // 多次 dijkstra 要清空 vis 数组
    dis[s]=0; // 源点距离赋值为 0
    priority_queue<node>Q;
    Q.push((node){s,0}); // 将源点的数据压入队列中
    while(Q.size())
    {
        int x=Q.top().pos; // 取队列元素所表示的端点编号
        Q.pop(); // 将该元素弹出
        if(vis[x])continue;
        vis[x]=true;
        // 判断是否被访问 + 标记访问
        for(int i=head[x];i;i=e[i].nxt) // 运用链式前向星的性质遍历
        {
            int y=e[i].to;
            if(e[i].f<minf)continue; // 如果该边的 f 值小于本次 dijkstra 所枚举的 minf 值，则跳过该边
            if(dis[y]>dis[x]+e[i].w) // 按照模板找最小距离
            {
                dis[y]=dis[x]+e[i].w;
                if(!vis[y])Q.push((node){y,dis[y]});
            }
        }
    }
    return dis[n];
}
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),c=read(),f=read();
        add(u,v,c,f);
        add(v,u,c,f);
        // 无向图，需存两次边
        F[i]=f;
    }
    for(int i=1;i<=m;i++)ans=max(ans,1e6*F[i]/dijkstra(1,F[i]));
    // 把 ans 值赋值为当前枚举到的 minf 和 dijkstra 后得到最小距离的商的 1e6 倍
    printf("%d",int(ans)); // 下取整输出答案
    return 0;
}

$\text{Solution 2: 标记}$

实际上，我们在 $\text{Dijkstra}$ 的过程中，可以在边的结构体再加一些变量来保存 $f$ 和 $c$，并用浮点类型记录 $\dfrac{\min\{f_i\}}{\sum c_i}$ 的值。

时间复杂度：$\mathcal O((n+m) \log n)$

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,head[1001];
double dis[1001];
bool vis[1001];
struct edge
{
    int nxt,to,w,f;
}e[2001];
struct node
{
    int pos,f,dis;
    // f 保存遍历过程中，经过的 f 值中最小的
    double d;
    // 比前一份代码中多了 d 和 f 两个变量，实际上 d = f / dis
    bool operator<(const node &x)const
    {
        return d<x.d;
    }
    // 实际上应该让 d 更大的在前面，但与前面同理，需要颠倒
};
void add(int u,int v,int w,int f)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].f=f;
    head[u]=cnt;
}
double dijkstra(int s)
{
    memset(vis,false,sizeof(vis));
    priority_queue<node>Q;
    Q.push((node){s,0x3f3f3f3f,0,0});
    // 源点编号为 s，而 f 的最小值应当设为 0x3f3f3f3f
    while(Q.size())
    {
        int x=Q.top().pos,f=Q.top().f,d=Q.top().dis;
        Q.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to,nd=d+e[i].w,nf=min(f,e[i].f);
            // nd 记录编号 1 和 y 两个点之间的距离
            // nf 取当前 f 值和之前所有 f 值中最小的
            if(1.0*nf/nd>dis[y]) // 我们要求的是最大的 nf/nd，所以按照这个值的大小进行松弛
            {
                dis[y]=1.0*nf/nd;
                if(!vis[y])Q.push((node){y,nf,nd,dis[y]});
            }
        }
    }
    return dis[n];
}
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),c=read(),f=read();
        add(u,v,c,f);
        add(v,u,c,f);
    }
    printf("%d",int(1e6*dijkstra(1))); // 直接输出跑一次 dijkstra 得到的值即可
    return 0;
}

祝大家 $\text{NOIP2020 RP++}$！