Luogu P2888 [USACO07NOV]Cow Hurdles S problem solution

Title Link: P2888 [USACO07NOV]Cow Hurdles S

Farmer John wants her cows ready for the county jump race. Bessie and her partners are practicing hurdles. They are very tired, so they want to use the least energy to cross the hurdles. Obviously, it is easy for a cow to jump over several low hurdles, but it is difficult for a cow to jump over high hurdles. Therefore, the cows always care about the height of the highest column on the path. There are cows in the training ground N ( 1 ≤ N ≤ 300 ) N (1 ≤ N ≤ 300) N(1 ≤ n ≤ 300) platforms, marked as 1 ... N 1\dots N 1…N . Between all platforms M ( 1 ≤ M ≤ 25 , 000 ) M (1 ≤ M ≤ 25,000) M(1 ≤ m ≤ 25000) one-way paths, and the i-way path is from the platform S i S_i Si ， start, get to the platform E i E_i Ei, where the height of the highest column is H i ( 1 ≤ H i ≤ 1 , 000 , 000 ) H_i (1 ≤ H_i ≤ 1,000,000) Hi​(1≤Hi​≤1,000,000). No matter how they run, the cows have to hurdle. Cows have T ( 1 ≤ T ≤ 40 , 000 ) T (1 ≤ T ≤ 40,000) T(1 ≤ t ≤ 40000) training tasks need to be completed. The first i i i tasks contain two numbers A i A_i Ai and B i ( 1 ≤ A i ≤ N ; 1 ≤ B i ≤ N ) B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N) Bi (1 ≤ Ai ≤ N;1 ≤ Bi ≤ N), indicating that the cow must leave the platform A i A_i Ai runs to the platform B i B_i Bi, you can pass other platforms. The cows want to find a way from the platform A i A_i Ai: get to the platform B i B_i Bi to minimize the height of the highest column on the path. Your task is to write a program to calculate the minimum height of the highest column on the path.

By analyzing the topic, we can find that this is a directed graph with non negative weight

We only need to find a path to minimize the maximum of all the edge weights on this path

Floyd solution

Don't look at this n ≤ 300 n\le300 n ≤ 300, still running fast (the data is a little water)

It is easy to deduce the equation f[i][j]=min(f[i][j],max(f[i][k],f[k][j]);

But I was a little worried, so I added a small pruning qwq, although it was only 3ms fast

The code is as follows

//Floyd
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
int n,m,Q,f[305][305],g[305][305];
signed main()
{
    read(n);read(m);read(Q);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=g[i][j]=INF;
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        g[u][v]=min(g[u][v],w);
        f[u][v]=min(f[u][v],w);
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            if(f[i][k]!=INF)
                for(int j=1; j<=n; j++)
                    f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
    while(Q--)
    {
        int x,y;read(x);read(y);
        write((f[x][y]==INF)?-1:f[x][y]);pc('\n');
    }
    return 0;
}

Other solutions

About SPFA, she's dead.

just a joke

However, we can use dijkstra with low theoretical complexity

be aware N ≤ 300 N\le300 N≤300

Then it can be solved offline

Time complexity O ( N 2 log ⁡ M + T ) O(N^2\log M + T) O(N2logM+T)

But in fact, due to the large dijkstra constant, it runs even slower than Floyd

The code is as follows

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
struct Edge
{
    int u,v,w,next;
}e[50005];
struct node
{
    int u,mn;
    bool operator<(const node &o)const
    {
        return mn>o.mn;
    }
};
int pos=1,head[305];
int n,m,Q,d[305][305],vis[305];
void addEdge(int u,int v,int w)
{
    e[pos]={u,v,w,head[u]};
    head[u]=pos++;
}
void dijkstra(int st)
{
    priority_queue<node> q;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
        d[st][i]=INF;
    q.push({st,INF});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,t=max(d[st][u],e[i].w);
            if(t==INF)t=e[i].w;
            if(d[st][v]>t)
            {
                d[st][v]=t;
                if(!vis[v])
                    q.push({v,d[st][v]});
            }
        }
    }
}
signed main()
{
    read(n);read(m);read(Q);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        addEdge(u,v,w);
    }
    for(int i=1; i<=n; i++)
        dijkstra(i);
    while(Q--)
    {
        int x,y;read(x);read(y);
        write((d[x][y]==INF)?-1:d[x][y]);pc('\n');
    }
    return 0;
}

Reprint, please indicate the source