题意:农民约翰的农场有一套老旧的管网，管网由M条管道(1<=M<=500)构成，用于将牛奶从谷仓运到储奶罐.他想在明年移除和更新大部分管道，但他想原封不动地保留一条完整的路径，这样他仍然可以把牛奶从谷仓输送到储罐.管网由N个节点(1<=N<=500)组成，每个点都可以作为一组管道的端点.结点1是谷仓，结点N是储罐。M条双向管道中的每一条都连接一对节点，并且都有一个延迟值(牛奶达到管的另一端的用时)和容量值(单位时间内可以稳定通过管道的牛奶量)。多条管道可以连接同一对节点.对于一条连接谷仓与储罐的路径，路径的延迟等于沿途所有管道的延迟之和，路径的容量等于沿途管道最小的容量(因为这是制约牛奶运送的“瓶颈”).如果约翰通过一条延迟为L、容量为C的管道运送X个单位的牛奶，需要的时间为L+X/C.给出约翰的管网结构，请帮助他选择一条路径，使得他从谷仓到储罐运送X个单位牛奶的总时间最少.
分析:刚开始看题面还以为是网络流呢,然后问题随机一转?就是一道最短路题了.有点像通往奥格瑞玛的道路,但是这题还容易些,不需要二分答案,而是直接枚举最小容量即可.枚举最小容量之后跑最短路即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=505;
int n,m,x,ans=1e9,visit[N],dis[N],rl[N];
int tot,head[N],nxt[N<<1],to[N<<1],w1[N<<1],w2[N<<1];
inline void add(int a,int b,int c,int d){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w1[tot]=c;w2[tot]=d;
}
queue<int>q;
inline void spfa(int maxn){
for(int i=1;i<=n;++i)dis[i]=1e9,visit[i]=0;
q.push(1);visit[1]=1;dis[1]=0;
while(q.size()){
int u=q.front();q.pop();visit[u]=0;
for(int i=head[u];i;i=nxt[i]){
if(w2[i]<maxn)continue;//不符合最小容量要求
int v=to[i];
if(dis[v]>dis[u]+w1[i]){
dis[v]=dis[u]+w1[i];
if(!visit[v]){
visit[v]=1;
q.push(v);
}
}
}
}
}
int main(){
n=read(),m=read(),x=read();
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read(),d=read();
add(a,b,c,d);add(b,a,c,d);rl[i]=d;
}
sort(rl+1,rl+m+1);//从小到大排序,方便枚举
for(int i=1;i<=m;++i){
spfa(rl[i]);//跑最短路
ans=min(ans,dis[n]+(int)x/rl[i]);
}
printf("%d\n",ans);
return 0;
}