[kuangbin带你飞]专题四 最短路练习

时间：2023-02-13 19:59:39

A - Til the Cows Come Home

题意：最短路模板题

思路：没什么好说的，直接上SPFA，见代码

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef  long long ll;
const int MAXN=2500;
const int INF=0x3f3f3f3f;
int dist[MAXN];
bool visit[MAXN];
struct node
{
    int to;
    int lens;
};
vector<node > mp[MAXN];
int n,m,s,t;
void spfa()
{
    memset(dist,INF,sizeof(dist));
    memset(visit,0,sizeof(visit));
    queue<int >q;
    q.push(1);
    visit[1]=1;
    dist[1]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        visit[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            if(dist[mp[now][i].to]>dist[now]+mp[now][i].lens)
            {
                dist[mp[now][i].to]=dist[now]+mp[now][i].lens;
                if(visit[mp[now][i].to]==0)
                {
                    q.push(mp[now][i].to);
                    visit[mp[now][i].to]=1;
                }
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        for(int i=1;i<=n;i++)
            mp[i].clear();
        s=1,t=n;
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            node next;
            next.to=y,next.lens=z;
            mp[x].push_back(next);
            next.to=x,next.lens=z;
            mp[y].push_back(next);
        }
        spfa();
        printf("%d\n",dist[n]);

    }

    return 0;
}

 B - Frogger

题意：这题难点主要在题意，简单来说就是两只青蛙，求青蛙1到青蛙2的所有路径上最大边权的最小值。

思路：可以把最短路算法里的距离数组改存为到起点到i点的最大边权的最小值即可。

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef  long long ll;
const int MAXN=250;
const double INF=0x3f3f3f3f;
double dist[MAXN];
bool visit[MAXN];
struct node
{
    int to;
    double lens;
};
int x[MAXN],y[MAXN];
vector<node > mp[MAXN];
int n,m,s,t;
void spfa()
{
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    memset(visit,0,sizeof(visit));
    queue<int >q;
    q.push(1);
    visit[1]=1;
    dist[1]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        visit[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            if(dist[mp[now][i].to]>max(dist[now],mp[now][i].lens))
            {
                dist[mp[now][i].to]=max(dist[now],mp[now][i].lens);
                if(visit[mp[now][i].to]==0)
                {
                    q.push(mp[now][i].to);
                    visit[mp[now][i].to]=1;
                }
            }
        }
    }
}
int main()
{
    int tot=0;
    while(scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            mp[i].clear();
        s=1,t=2;
        for(int i=1;i<=n;i++) {
            scanf("%d%d", &x[i], &y[i]);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(i==j) continue;
                node next;
                next.to=j,next.lens=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                mp[i].push_back(next);
            }
        spfa();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",++tot,dist[2]);

    }

    return 0;
}

 C - Heavy Transportation

题意：跟上题类似，求点1到点n的所有路径上最小边权的最大值。

思路：可以把最短路算法里的距离数组改存为到起点到i点的最小边权的最大值即可。

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef  long long ll;
const int MAXN=1250;
const int INF=0x3f3f3f3f;
int dist[MAXN];
bool visit[MAXN];
struct node
{
    int to;
    int lens;
};
vector<node> mp[MAXN];
int n,m,t,x,y,z;
void spfa()
{
    for(int i=1;i<=n;i++)
        dist[i]=0;
    memset(visit,0,sizeof(visit));
    queue<int >q;
    q.push(1);
    visit[1]=1;
    dist[1]=INF;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        visit[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            if(dist[mp[now][i].to]<min(dist[now],mp[now][i].lens))
            {
                dist[mp[now][i].to]=min(dist[now],mp[now][i].lens);
                if(visit[mp[now][i].to]==0)
                {
                    q.push(mp[now][i].to);
                    visit[mp[now][i].to]=1;
                }
            }
        }
    }
}
int main()
{
    int tot=0;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            mp[i].clear();
        for(int i=1;i<=m;i++) {
            scanf("%d%d%d", &x,&y,&z);
            node next;
            next.to=y,next.lens=z;
            mp[x].push_back(next);
            next.to=x,next.lens=z;
            mp[y].push_back(next);
        }
        spfa();
        printf("Scenario #%d:\n%d\n\n",++tot,dist[n]);

    }

    return 0;
}

 D - Silver Cow Party

题意：给出n个点和m条边，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找出一个最大值输出

思路：很明显要求两次最短路。因为边是有向边，我们可以把一条边正向存在一个图里，反向存在另一张图里。对两张图分别从x开始跑一次最短路。最多枚举答案即可。

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef  long long ll;
const int MAXN=2250;
const int INF=0x3f3f3f3f;
int dist1[MAXN];
int dist2[MAXN];
bool visit[MAXN];
struct node
{
    int to;
    int lens;
};
vector<node>mp1[MAXN];
vector<node>mp2[MAXN];
int n,m,x,a,b,c;
void spfa1()
{
    memset(dist1,INF,sizeof(dist1));
    memset(visit,0,sizeof(visit));
    queue<int >q;
    q.push(x);
    visit[x]=1;
    dist1[x]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        visit[now]=0;
        for(int i=0;i<mp1[now].size();i++)
        {
            if(dist1[mp1[now][i].to]>dist1[now]+mp1[now][i].lens)
            {
                dist1[mp1[now][i].to]=dist1[now]+mp1[now][i].lens;
                if(visit[mp1[now][i].to]==0)
                {
                    q.push(mp1[now][i].to);
                    visit[mp1[now][i].to]=1;
                }
            }
        }

    }
}
void spfa2()
{
    memset(dist2,INF,sizeof(dist2));
    memset(visit,0,sizeof(visit));
    queue<int >q;
    q.push(x);
    visit[x]=1;
    dist2[x]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        visit[now]=0;
        for(int i=0;i<mp2[now].size();i++)
        {
            if(dist2[mp2[now][i].to]>dist2[now]+mp2[now][i].lens)
            {
                dist2[mp2[now][i].to]=dist2[now]+mp2[now][i].lens;
                if(visit[mp2[now][i].to]==0)
                {
                    q.push(mp2[now][i].to);
                    visit[mp2[now][i].to]=1;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
    {

        for(int i=1;i<=n;i++)
        {
            mp1[i].clear();
            mp2[i].clear();
        }
        for(int i=1;i<=m;i++) {
            scanf("%d%d%d",&a,&b,&c);
            node next;
            next.to=b,next.lens=c;
            mp1[a].push_back(next);
            next.to=a,next.lens=c;
            mp2[b].push_back(next);
        }
        spfa1();
        spfa2();
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,dist1[i]+dist2[i]);
        printf("%d\n",ans);

    }

    return 0;
}

 

 E - Currency Exchange

题意：在某一点有第s种货币V元。给出每个兑换点的兑换汇率和佣金。问通过兑换能否使钱增长。

思路：按照题意建立有向图。问题转化为从S出发回到S能否使值增大。spfa+判断即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 210;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,s;
double v;
struct node
{
    int to;
    double h;
    double f;
};
double dist[N];
bool vis[N];
vector<node> mp[N];
void init()
{
    for(int i=1;i<=N;i++)
        dist[i]=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=N;i++)
        mp[i].clear();
}
int  spfa()
{
    vis[s]=1;
    dist[s]=v;
    queue<int >q;
    q.push(s);
    while(!q.empty())
    {
        int  now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            if(dist[mp[now][i].to]<mp[now][i].h*(dist[now]-mp[now][i].f))
            {
                dist[mp[now][i].to]=mp[now][i].h*(dist[now]-mp[now][i].f);
                if(vis[mp[now][i].to]==0)
                {
                    vis[mp[now][i].to]=1;
                    q.push(mp[now][i].to);
                }
            }
        }
        if(now==s&&dist[now]>v) return 1;
    }
    return 0;
}

int main()
{
    while(cin>>n>>m>>s>>v)
    {
        init();
        int a,b;
        double c,d,e,f;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b>>c>>d>>e>>f;
            node next;
            next.to=b,next.h=c,next.f=d;
            mp[a].push_back(next);
            next.to=a,next.h=e,next.f=f;
            mp[b].push_back(next);
        }
        if(spfa()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

 

F - Wormholes

题意：有中文题面。简单说就是判负圈模板题。

思路：spfa判负圈：一个点入队超过n次即存在负圈。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 510;
typedef long long ll;
const int INF=0x3f3f3f3f;
int t,n,w,m;
struct node
{
    int to;
    int road;
};
int dist[N];
bool vis[N];
int use[N];
vector<node> mp[N];
void init()
{
    memset(dist,INF,sizeof(dist));
    memset(vis,0,sizeof(vis));
    memset(use,0,sizeof(use));
    for(int i=1;i<=N;i++)
        mp[i].clear();
}
int  spfa()
{
    int s=1;
    vis[s]=1;
    dist[s]=0;
    queue<int >q;
    q.push(s);
    use[s]++;
    while(!q.empty())
    {
        int  now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            if(dist[mp[now][i].to]>dist[now]+mp[now][i].road)
            {
                dist[mp[now][i].to]=dist[now]+mp[now][i].road;
                if(vis[mp[now][i].to]==0)
                {
                    vis[mp[now][i].to]=1;
                    use[mp[now][i].to]++;
                    q.push(mp[now][i].to);
                    if(use[mp[now][i].to]>n) return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    cin>>t;
    while(t--)
    {
        init();
        cin>>n>>m>>w;
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y>>z;
            node next;
            next.to=y,next.road=z;
            mp[x].push_back(next);
            next.to=x,next.road=z;
            mp[y].push_back(next);
        }
        for(int i=1;i<=w;i++)
        {
            cin>>x>>y>>z;
            node next;
            next.to=y;
            next.road=-z;
            mp[x].push_back(next);
        }
        if(spfa()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

 

标签：

相关文章