【luogu P3063 [USACO12DEC]牛奶的路由Milk Routing】 题解

题目链接：https://www.luogu.org/problemnew/show/P3063#sub

我很好奇这道题为什么没被收入SPFA好题

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int inf = 0x7fffffff-;

 int n, m, s, f, x, k, ans = inf, dis[maxn], c[maxn];

 bool vis[maxn];

 struct edge{

     int to, next, len, from, l;

 }e[maxn];

 int head[maxn], cnt;

 void add(int u, int v, int w, int l)

 {

     e[++cnt].from = u;

     e[cnt].to = v;

     e[cnt].len = w;

     e[cnt].l = l;

     e[cnt].next = head[u];

     head[u] = cnt;

 }

 int SPFA(int k)

 {

     queue<int> q;

     memset(vis,,sizeof(vis));

     memset(dis,,sizeof(dis));

     dis[s] = ;

        q.push(s);

     vis[s] = ;

     while(!q.empty())

     {

         int now = q.front();

         q.pop();

         vis[now] = ;

         for(int i = head[now]; i ; i = e[i].next)

         {

             if(dis[e[i].to] > dis[now]+e[i].len && e[i].l >= k)

             {

                 dis[e[i].to] = dis[now]+e[i].len;

                 if(!vis[e[i].to])

                 {

                     vis[e[i].to] = ;

                     q.push(e[i].to);

                 }

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&x);

     for(int i = ; i <= m; i++)

     {

         int u,v,w,l;

         scanf("%d%d%d%d",&u,&v,&w,&l);

         add(u,v,w,l);

         add(v,u,w,l);

         c[i] = l;

     }

     sort(c+,c+m+);

     s = , f = n;

     for(int i = ; i <= m; i++)

     {

         SPFA(c[i]);

         ans = min(ans, dis[f]+x/c[i]);

     }

     printf("%d",ans);

 }