专题四 最短路练习

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

1.Til the Cows Come Home

题目链接:https://vjudge.net/problem/POJ-2387
题目大意:1为谷仓,n为她目前的位置,求回谷仓的最短路
解题思路:Dijkstra,本以为铁头三个for能过,,,结果撞墙了,改良版Dijkstra模板
代码:

#include <iostream>
#include <cstring>
#define MAX 0x3f3f3f3f
using namespace std;
int mp[1100][1100],lowcost[1100];
bool vis[1100];
int t,n;

void d()
{
    lowcost[1]=0;//初始点
    for(int j=1;j<=n;j++)
    {
        int k=-1;
        int Min=MAX;
        for(int i=1;i<=n;i++)//找最小值
        {
            if(!vis[i]&&lowcost[i]<Min)
            {
                Min=lowcost[i];
                k=i;
            }
        }
        if(k==-1)break;
        vis[k]=true;
        for(int i=1;i<=n;i++)//更新
        {
            if(!vis[i]&&lowcost[k]+mp[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+mp[k][i];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int u,v,l;
    cin>>t>>n;
    memset(mp,MAX,sizeof(mp));
    for(int i=0;i<=1010;i++)
    {
        mp[i][i]=0;
    }
    memset(vis,false,sizeof(vis));
    memset(lowcost,MAX,sizeof(lowcost));
    for(int i=0;i<t;i++)
    {
        cin>>u>>v>>l;
        if(mp[u][v]>l)
        mp[u][v]=mp[v][u]=l;
    }
    d();
    cout<<lowcost[n]<<endl;
    return 0;
}

2.Frogger

题目链接:https://vjudge.net/problem/POJ-2253
题目大意:一只青蛙想要从2号荷叶到1号荷叶,问每条路径里最长路中的最短路的长度
解题思路:魔改Dijkstra,更新dis数组时选最大值更新
代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <stdio.h>
#define MAX 9999999
using namespace std;
int n,vis[220];
double mp[220][2],ans,dis[220],cost[220][220],minn;
void d()
{
    dis[1]=0;
    int k;
    for(int j=0;j<n;j++)
    {
        minn=MAX;
        for(int i=0;i<n;i++)//确定dis,中的最短路,min
        {
           if(!vis[i]&&dis[i]<minn)
           {
                minn=dis[i];
                k=i;
           }
        }
        vis[k]=1;
        for(int i=0;i<n;i++)//更新距离,最长路,max
        {
            if(!vis[i]&&dis[i]>max(dis[k],cost[k][i]))
            {
                dis[i]=max(dis[k],cost[k][i]);
            }
        }
    }
}
int main()
{
    for(int k=1;k;k++)
    {
        cin>>n;
        if(!n)
        {
            break;
        }
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                cost[i][j]=MAX;
            }
            cost[i][i]=0;
            dis[i]=MAX;
        }
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            cin>>mp[i][0]>>mp[i][1];
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)continue;
                ans=pow((mp[i][0]-mp[j][0])*(mp[i][0]-mp[j][0])+
                        (mp[i][1]-mp[j][1])*(mp[i][1]-mp[j][1]),1.0/2);
                if(cost[i][j]>ans)cost[i][j]=ans;
            }
        } 
        d();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",k,dis[0]);
    }
    return 0;
}

3.Heavy Transportation

题目链接:https://vjudge.net/problem/POJ-1797
题目大意:一个地图,现在要从1向n送东西,每条路都有自己的限重,问最多可以送多重的东西,也就是求每条路中最小值中的最大值。
解题思路:参照上一个代码,魔改
代码:

#include <iostream>
#include <cstring>
using namespace std;
int n,m;
long long int mp[1100][1100],vis[1100],dis[1100];
void di()
{
    dis[1]=0x3f3f3f3f;
    for(int j=0; j<n; j++)
    {
        int maxx=-1;
        int k;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i]&&dis[i]>maxx)//2.最长路
            {
                maxx=dis[i];
                k=i;
            }
        }
        vis[k]=1;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i]&&min(dis[k],mp[k][i])>dis[i])//1.最短路的
            {
                dis[i]=min(dis[k],mp[k][i]);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    long long int u,v,w;
    cin>>t;
    for(int k=1; k<=t; k++)
    {
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        memset(dis,0,sizeof(dis));
        cin>>n>>m;
        for(int i=0; i<m; i++)
        {
            cin>>u>>v>>w;
            mp[u][v]=mp[v][u]=w;
        }
        di();
        cout<<"Scenario #"<<k<<":"<<endl;
        cout<<dis[n]<<endl<<endl;
    }
    return 0;
}

4.Silver Cow Party

题目链接:https://vjudge.net/problem/POJ-3268
题目大意:农场,cong1到n编号,在x举办聚会,所有的动物都从自己的农场走去聚会然后再回去,这个过程中动物会走最短的路,问所有动物中走动距离最大的是多少
解题思路:首先用最短路算出x到所有动物的最短距离,这是每个动物聚会结束后回家所要走的最短距离,然后翻转每条路的两个端点(1到2长度为3改为2到1长度为三,翻转二维数组即可),再求一边x到所有动物的最短距离,这是每个动物去x的最短距离,两者相加求最大值即可
代码:

#include <iostream>
#include <cstring>

using namespace std;

int n,m,x,mp[1100][1100],vis[1100],dis[1100],a[1100][1100],dis_a[1100];
void f()//回家最短路
{
    dis[x]=0;
    for(int i=1;i<=n;i++)
    {
        int minn=0x3f3f3f3f,k;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j];
                k=j;
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>dis[k]+mp[k][j])
            {
                dis[j]=dis[k]+mp[k][j];
            }
        }
    }
}

void f_a()//去聚会最短路
{
    dis_a[x]=0;
    for(int i=1;i<=n;i++)
    {
        int minn=0x3f3f3f3f,k;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis_a[j]<minn)
            {
                minn=dis_a[j];
                k=j;
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis_a[j]>dis_a[k]+a[k][j])
            {
                dis_a[j]=dis_a[k]+a[k][j];
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>x;
    memset(mp,0x3f3f3f3f,sizeof(mp));
    memset(a,0x3f3f3f3f,sizeof(a));
    for(int i=0; i<=n; i++)
    {
        mp[i][i]=0;
        a[i][i]=0;
    }
    int u,v,l;
    for(int i=0; i<m; i++)
    {
        cin>>u>>v>>l;
        if(l<mp[u][v])
            mp[u][v]=l;
        if(l<a[v][u])
            a[v][u]=l;
    }
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    f();
    memset(vis,0,sizeof(vis));
    memset(dis_a,0x3f3f3f3f,sizeof(dis_a));
    f_a();
    int maxx=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]+dis_a[i]>maxx)
        {
            maxx=dis[i]+dis_a[i];
        }
    }
    cout<<maxx<<endl;
    return 0;
}

5.Currency Exchange

题目链接:https://vjudge.net/problem/POJ-1860
题目大意:每个点之间都有一个汇率和手续费,(假设他在a点有b元,b到c的手续费为d元,汇率为e元,到c时他有(b – d) * e元,)现在他有v元在s点处,问能不能通过不断地兑换货币使得最终回到s点时有更多的钱。
解题思路:这个题的关键在于判断是否存在正权回路,只要存在正权回路就一定输出yes否则一定输出no,于是spfa或Bellman-Ford就正好可以解决(Bellman-Ford
代码:
SPFA版

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=110;
int n,m,s;
double dis[N],v,rate[N][N],cost[N][N];
int cnt[N];//cnt数组用来存储每个点松弛了几次
bool spfa(int start)
{
    bool inq[110];
    memset(inq,0,sizeof(inq));
    memset(dis,0,sizeof(dis));
    dis[start]=v;
    queue<int>q;
    q.push(start);
    inq[start]=true;
    cnt[start]=1;
    while(!q.empty())
    {
        int x=q.front();
        if(cnt[x]>n)//若存在点松弛次数超过了点的总数,就是说存在正权回路,返回1
            return true;
        q.pop();
        inq[x]=false;
        for(int i=1;i<=n;i++)
        {
            if(dis[i]<(dis[x]-cost[x][i])*rate[x][i])
            {
                dis[i]=(dis[x]-cost[x][i])*rate[x][i];
                if(!inq[i])
                {
                    cnt[i]++;
                    q.push(i);
                    inq[i]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    while(cin>>n>>m>>s>>v)
    {
        int a,b;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)rate[i][j]=1;
                else rate[i][j]=0;
                cost[i][j]=0;
            }
        }
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            cin>>rate[a][b]>>cost[a][b]>>rate[b][a]>>cost[b][a];
        }
        memset(cnt,0,sizeof(cnt));
        if(spfa(s))
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }
    return 0;
}

Bellman-Ford版

#include <iostream>
#include <cstring>
using namespace std;
int n,m,s,cc;
double v,dis[110];
struct point
{
    int a,b;
    double rate,cost;
}p[500];
bool bb()
{
    memset(dis,0,sizeof(dis));
    dis[s]=v;
    for(int i=1;i<=n-1;i++)//n-1次松弛后一定可以完成无正权回路的图的松弛
    {
        bool flag=false;
        for(int j=0;j<cc;j++)
        {
            int a=p[j].a;
            int b=p[j].b;
            double r=p[j].rate;
            double c=p[j].cost;
            if(dis[b]<(dis[a]-c)*r)
            {
                dis[b]=(dis[a]-c)*r;
                flag=true;
            }
        }
        if(!flag)
        {
            break;
        }
    }
    for(int i=0;i<cc;i++)//若还可以松弛,说明存在正权回路
    {
        if(dis[p[i].b]<(dis[p[i].a]-p[i].cost)*p[i].rate)
            return true;
    }
    return false;
}
int main()
{
    int a,b;
    while(cin>>n>>m>>s>>v)
    {
        cc=0;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            p[cc].a=a;
            p[cc].b=b;
            cin>>p[cc].rate;
            cin>>p[cc].cost;
            cc++;
            p[cc].a=b;
            p[cc].b=a;
            cin>>p[cc].rate;
            cin>>p[cc].cost;
            cc++;
        }
        if(bb())
          cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

6.Wormholes

题目链接:https://vjudge.net/problem/POJ-3259
题目大意:有n个点,m条双向路通过路需要花费时间,w条虫洞,虫洞可以将时间向前推一段时间,问可不可以通过走路与穿越虫洞来使回到起点的时间早于从起点出发的时间
解题思路:和上一道题基本相同,寻找有无负权回路
代码:

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m,l;
int mp[550][550],a[550][550];
int inq[550],cnt[550],dis[550];
int spfa()
{
    queue<int>q;
    inq[1]=1;
    cnt[1]=1;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        if(cnt[u]>n)
        {
            return 1;
        }
        for(int i=1;i<=n;i++)
        {
            if(dis[i]>dis[u]+mp[u][i])
            {
                dis[i]=dis[u]+mp[u][i];
                if(!inq[i])
                {
                    inq[i]=1;
                    cnt[i]++;
                    q.push(i);
                }
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    int F;
    cin>>F;
    int u,v,w;
    while(F--)
    {
        memset(mp,0x3f3f3f3f,sizeof(mp));
        cin>>n>>m>>w;
        for(int i=0; i<=n; i++)
        {
            mp[i][i]=0;
        }
        for(int i=0; i<m; i++)
        {
            cin>>u>>v>>l;
            if(mp[u][v]>l)
                mp[u][v]=mp[v][u]=l;
        }
        for(int i=0; i<w; i++)
        {
            cin>>u>>v>>l;
            if(mp[u][v]>-l)
                mp[u][v]=-l;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                a[i][j]=mp[i][j];
            }
        }
        memset(cnt,0,sizeof(cnt));
        memset(inq,0,sizeof(inq));
        memset(dis,0x3f3f3f3f,sizeof(dis));
        if(spfa())cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

7.MPI Maelstrom

题目链接
题目大意:有n台计算机,两两之间的传输时间给出,问到每个点的最短时间里的最大值
解题思路:数据量很小,三层for循环搞定
代码

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    int mp[110][110];
    char c[10010];
    cin>>n;
    memset(mp,0,sizeof(mp));
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            cin>>c;
            if(c[0]=='x')
            {
                mp[i][j]=0x3f3f3f3f;
            }
            else
            {
                int l=strlen(c),w=1;
                mp[i][j]=0;
                for(int k=l-1; k>=0; k--)
                {
                    mp[i][j]+=(c[k]-'0')*w;
                    w*=10;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        mp[i][i]=0;
    }
    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            mp[i][j]=mp[j][i];
        }
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(mp[i][k]==0x3f3f3f3f||mp[k][j]==0x3f3f3f3f)
                    continue;
                if(mp[i][j]>mp[i][k]+mp[k][j])
                {
                    mp[i][j]=mp[i][k]+mp[k][j];
                }
            }
        }
    }
    int maxx=-1;
    for(int i=2; i<=n; i++)
    {
        maxx=max(maxx,mp[1][i]);
    }
    cout<<maxx<<endl;
    return 0;
}

8.Cow Contest

题目链接:https://cn.vjudge.net/problem/POJ-3660
题目大意:给出n对奶牛,每对奶牛的前者都会战胜后者,问最终能确定名次的奶牛数量
解题思路:这道题以前在离散数学的机考中遇到过,但当时感觉好难就把代码背过了,如今再看好像并没有多难
一头牛的名次确定的充分条件是他与其他的n-1头牛都有战败、胜关系,用floyed可求
代码

#include <iostream>
#include <cstring>

using namespace std;
int mp[110][110];
int n,m;

void f()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                mp[i][j]=mp[i][j]||(mp[i][k]&&mp[k][j]);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int a,b;
    cin>>n>>m;
    memset(mp,0,sizeof(mp));
    for(int i=0; i<m; i++)
    {
        cin>>a>>b;
        mp[a][b]=1;
    }
    f();
    int ans=0;
    int sum;
    for(int i=1;i<=n;i++)
    {
        sum=0;
        for(int j=1;j<=n;j++)
        {
            if(mp[i][j]||mp[j][i])sum++;
        }
        if(sum==n-1)
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

9.Arbitrage

题目链接:https://cn.vjudge.net/problem/POJ-2240
题目大意:和前面的一道汇率题一样,问能不能通过给定的汇率不断兑换货币来赚钱
解题思路:spfa判断正权回路
代码

#include <iostream>
#include <map>
#include <queue>
#include <cstring>
using namespace std;

double mp[33][33];
int n;

int spfa()
{
    int inque[33],cnt[33];
    double dis[33];
    memset(inque,0,sizeof(inque));
    memset(cnt,0,sizeof(cnt));
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(0);
    inque[0]=1;
    dis[0]=1;
    cnt[0]++;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inque[u]=0;
        if(cnt[u]>n)
        {
            return 1;
        }
        for(int i=0;i<n;i++)
        {
            if(dis[i]<dis[u]*mp[u][i]*1.0)
            {
                dis[i]=dis[u]*mp[u][i]*1.0;
                if(!inque[i])
                {
                    q.push(i);
                    inque[i]=1;
                    cnt[i]++;
                }
            }
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    int kk=0;
    while(cin>>n&&n)
    {
        memset(mp,0,sizeof(mp));
        for(int i=0;i<=n;i++)
        {
            mp[i][i]=1;
        }
        kk++;
        map<string,int> f;
        char d[35];
        for(int i=0; i<n; i++)
        {
            cin>>d;
            f[d]=i;
        }
        int m;
        cin>>m;
        char e[35];
        double h;
        for(int i=0;i<m;i++)
        {
            cin>>d>>h>>e;
            mp[f[d]][f[e]]=h;
        }
        if(spfa())cout<<"Case "<<kk<<": Yes"<<endl;
        else cout<<"Case "<<kk<<": No"<<endl;
    }
    return 0;
}

10.Invitation Cards

题目链接:https://cn.vjudge.net/problem/POJ-1511
题目大意:一些志愿者每天从1点到其他各点,然后再返回1点,往返路费不同,问最少一天要支付多少运费
解题思路:spfa求每一点到1点的正反最短路再将所有点相加即可,cin,cout会超时,动态数组会超时,要用结构体数组模拟
代码

#include <iostream>
#include <queue>
#include <cstring>
#include <stack>
#include <cstdio>

using namespace std;
struct node
{
    int to,w,next;
}e1[1000005],e2[1000005];
int head1[1000005],cnt1,head2[1000005],cnt2;
int dis1[1000005],dis2[1000005],vis[1000005];
int n,m;

void add1(int u,int v,int w)
{
    e1[cnt1].to=v;
    e1[cnt1].w=w;
    e1[cnt1].next=head1[u];
    head1[u]=cnt1++;
}

void add2(int u,int v,int w)
{
    e2[cnt2].to=u;
    e2[cnt2].w=w;
    e2[cnt2].next=head2[v];
    head2[v]=cnt2++;
}

void spfa1()
{
    memset(vis,0,sizeof(vis));
    memset(dis1,0x3f3f3f3f,sizeof(dis1));
    stack<int>q;
    q.push(1);
    dis1[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        vis[x]=0;
        for(int i=head1[x];i!=-1;i=e1[i].next)
        {
            int too=e1[i].to;
            int ww=e1[i].w;
            if(dis1[too]>dis1[x]+ww)
            {
                dis1[too]=dis1[x]+ww;
                if(!vis[too])
                {
                    vis[too]=1;
                    q.push(too);
                }
            }
        }
    }
}

void spfa2()
{
    memset(vis,0,sizeof(vis));
    memset(dis2,0x3f3f3f3f,sizeof(dis2));
    stack<int>q;
    q.push(1);
    dis2[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        vis[x]=0;
        for(int i=head2[x];i!=-1;i=e2[i].next)
        {
            int too=e2[i].to;
            int ww=e2[i].w;
            if(dis2[too]>dis2[x]+ww)
            {
                dis2[too]=dis2[x]+ww;
                if(!vis[too])
                {
                    vis[too]=1;
                    q.push(too);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cin>>n>>m;
        cnt1=0;
        cnt2=0;
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            //cin>>u>>v>>w;
            add1(u,v,w);
            add2(u,v,w);
        }
        spfa1();
        spfa2();
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=dis1[i]+dis2[i];
        }
        printf("%lld\n",sum);
        //cout<<sum<<endl;
    }
    return 0;
}

11.Candies

题目链接:https://cn.vjudge.net/problem/POJ-3159
题目大意:有n个孩子,分糖果,其中a承认b比他优秀,b理应获得比a更多的糖果,但如果b的糖果比a的糖果多于c的话,a就会非常非常不高兴。
现在让你在满足所给条件的同时,求第一个孩子最多可以比第n个孩子多多少个糖果。
解题思路:差分约束,详见zyl的博客
POJ日常cin,cout TLE。。。
代码:

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
using namespace std;
struct node
{
    int u,v,w,next;
}edge[200000];
int n,m;
int head[40000],cnt;
int dis[30005],vis[30005];

void add(int u,int v,int w)
{
    //edge[cnt].u=u;
    edge[cnt].w=w;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void spfa()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    stack<int>q;
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[v]>dis[x]+w)
            {
                dis[v]=dis[x]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //cin>>a>>b>>c;
        add(a,b,c);
    }
    spfa();
    printf("%d\n",dis[n]);
    //cout<<dis[n]<<endl;
    return 0;
}

12.Subway

题目链接:https://cn.vjudge.net/problem/POJ-2502
题目大意:首先给出两个点的坐标,代表家和学校,有多条地铁线路,分别给出站点的坐标,设地铁都是走直线切地铁以40km/h运行,同时还可以在任意站间步行,步行速度为10km/h
求从家到学校的最短时间花费
解题思路:首先题目并没有给出有多少条地铁线路,所以应用while循环输入,在windows里,文件结束的标识符是ctrl+z
其次难点就是建图了,由于地铁只能一站一站的跑,所以设输入的点为点n,只要计算并存入图中n-1到n的时间即可,建图详见代码
还有一个问题是memset,不能用memset给double类型的数组直接赋值
用spfa计算最短路
代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <cstdio>
using namespace std;

struct node
{
    double x,y;
} point[305];

double mp[305][305];
double v1=10000.0/60;
double v2=40000.0/60;
int vis[305];
double dis[305];

double dist(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void spfa(int n)
{
    for(int i=0;i<=n;i++)
    {
        dis[i]=0x3f3f3f3f;
    }
    stack<int>q;
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        vis[u]=0;
        for(int i=1; i<=n; i++)
        {
            if(dis[i]>dis[u]+mp[u][i])
            {
                dis[i]=dis[u]+mp[u][i];
                if(vis[i]==0)
                {
                    q.push(i);
                    vis[i]=1;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    for(int i=1;i<305;i++)
    {
        for(int j=1;j<305;j++)
        {
            mp[i][j]= i==j?0:0x3f3f3f3f;
        }
    }
    cin>>point[1].x>>point[1].y>>point[2].x>>point[2].y;
    double a,b;
    int n=2;
    int flag=1;
    while(cin>>a>>b)
    {
        if(a==-1&&b==-1)
        {
            flag=1;
            continue;
        }
        n++;
        point[n].x=a;
        point[n].y=b;
        if(flag)flag=0;
        else mp[n][n-1]=mp[n-1][n]=min(mp[n][n-1],dist(point[n],point[n-1])/v2);
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            mp[i][j]=mp[j][i]=min(mp[i][j],dist(point[i],point[j])/v1);
        }
    }
    spfa(n);
    long long ddd=dis[2]+0.5;
    cout<<ddd<<endl;
    return 0;
}

13.昂贵的聘礼

题目链接:https://cn.vjudge.net/problem/POJ-1062
题目大意:中文题
解题思路:mp[i][i]存该物品的价格,mp[i][j]为用j换i的优惠价格,这样求一下从1点到各点的单源最短路,所需的花费为到各点所需的最少优惠价格价格加上最终物品本身的价格;
需要注意的是等级差不能超过m,用两个for循环遍历即可,但要注意的是i-m到m的差为m,但i-m到i+m的差为2m
代码

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int n,m;
int mp[110][110],le[110],vis[110];

int di()
{
    int dis[110];
    memset(dis,0x3f3f3f3f,sizeof(dis));
    int ans=mp[1][1];
    dis[1]=0;
    int k;
    for(int j=0;j<n;j++)
    {
        int minn=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dis[i]<minn)
            {
                minn=dis[i];
                k=i;
            }
        }
        vis[k]=1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dis[i]>dis[k]+mp[k][i])
            {
                dis[i]=dis[k]+mp[k][i];
            }
        }
        dis[k]+=mp[k][k];
        ans=min(dis[k],ans);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;
    memset(mp,0x3f3f3f3f,sizeof(mp));
    for(int i=1;i<=n;i++)
    {
        int p,l,x;
        cin>>p>>l>>x;
        mp[i][i]=p;
        le[i]=l;
        for(int j=1;j<=x;j++)
        {
            int t,v;
            cin>>t>>v;
            mp[i][t]=v;
        }
    }
    int f;
    int ans=10000;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        f=0;
        for(int j=1;j<=n;j++)
        {
            if(le[j]-le[i]<=m&&le[j]-le[i]>=0)
            {
                if(j==1)f=1;
            }
            else vis[j]=1;
        }
        if(f==1)
        {
            ans=min(ans,di());
        }

        memset(vis,0,sizeof(vis));
        f=0;
        for(int j=1;j<=n;j++)
        {
            if(le[i]-le[j]<=m&&le[i]-le[j]>=0)
            {
                if(j==1)f=1;
            }
            else vis[j]=1;
        }
        if(f==1)
        {
            ans=min(ans,di());
        }
    }
    cout<<ans<<endl;
    return 0;
}

14.Tram

题目链接:https://cn.vjudge.net/problem/POJ-1847
题目大意:电车从a到b,在每个路口有很多岔道,只有第一个不用拨动开关,其他的都需要拨动
解题思路:数据量小,二维数组存图最短路即可
代码

#include <iostream>
#include <cstring>
using namespace std;
int n,a,b;
int mp[110][110],dis[110],vis[110];

void di()
{
    dis[a]=0;
    for(int i=0;i<n;i++)
    {
        int minn=0x3f3f3f3f,k;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j];
                k=j;
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(dis[j]>dis[k]+mp[k][j])
            {
                dis[j]=dis[k]+mp[k][j];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    int d,to;
    memset(mp,0x3f3f3f3f,sizeof(mp));
    for(int i=0;i<=n;i++)
    {
        mp[i][i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>d;
        for(int j=0;j<d;j++)
        {
            cin>>to;
            if(j==0)
            mp[i][to]=0;
            else mp[i][to]=1;
        }
    }

    memset(dis,0x3f3f3f3f,sizeof(dis));
    di();
    if(dis[b]==0x3f3f3f3f)cout<<"-1"<<endl;
    else
    cout<<dis[b]<<endl;
    return 0;
}

15.Extended Traffic

题目链接:https://cn.vjudge.net/problem/LightOJ-1074
题目大意:题意:n个城市,每个城市都有拥挤度,a点到b点的时间是(b拥挤度-a拥挤度)^3,第一个点是初始点,求最短路。
若不可能到达,或者小于3,就输出“?”
解题思路:建图,求最短路。
注意可能会有负权回路,用spfa
大意及思路来自zyl的博客
代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int a[220],mp[220][220];
int cnt[220],inque[220],dis[220];
int n;

void spfa()
{
    memset(inque,0,sizeof(inque));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    queue<int>q;
    inque[1]=1;
    dis[1]=0;
    q.push(1);
    cnt[1]++;
    while(!q.empty())
    {
        int d=q.front();
        q.pop();
        inque[d]=0;
        for(int i=1;i<=n;i++)
        {
            if(dis[i]>dis[d]+mp[d][i])
            {
                dis[i]=dis[d]+mp[d][i];
                if(!inque[i]&&cnt[i]<=n)
                {
                    inque[i]=1;
                    q.push(i);
                    cnt[i]++;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int kk=1;kk<=t;kk++)
    {
        memset(mp,0x3f3f3f3f,sizeof(mp));
        for(int i=1;i<=n;i++)
        {
            mp[i][i]=0;
        }
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int m;
        cin>>m;
        int u,v;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v;
            mp[u][v]=(a[v]-a[u])*(a[v]-a[u])*(a[v]-a[u]);
        }
        int q;
        cin>>q;
        int d;
        spfa();
        cout<<"Case "<<kk<<":"<<endl;
        for(int i=0;i<q;i++)
        {
            cin>>d;
            if(dis[d]<3||dis[d]==0x3f3f3f3f||cnt[d]>n)
            {
                cout<<"?"<<endl;
            }
            else cout<<dis[d]<<endl;
        }
    }
    return 0;
}

//2
//5
//6 7 8 9 10
//6
//1 2
//2 3
//3 4
//1 5
//5 4
//4 5
//2
//4
//5
//2
//10 10
//1
//1 2
//1
//2

16.The Shortest Path in Nya Graph

题目链接https://cn.vjudge.net/problem/HDU-4725
根本看不懂题QAQ
题目大意:有n层,每一层上有一些点,层内移动成本为0,相邻层见移动成本为c,一些特殊的点间可以直接移动成本为w,问从1到n的最小成本
解题思路:1-n存放点,将层抽象为点,存放在n后,层当做一个中间点,中间点到本层上的成本为0,然后建立相邻层间,点与点间,点与相邻层见的路
代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int n,m,k,c;
int head[200020],dis[200020];
int vv[200020],lay[200020];

struct node
{
    int v,m,next;
}edge[4000020];

bool vis[200020];
int cont[200020];

void add(int u,int v,int w)
{
    edge[k].m=w;
    edge[k].v=v;
    edge[k].next=head[u];
    head[u]=k++;
}

void spfa()
{
    memset(vis,0,sizeof(vis));
    queue<int>q;
    vis[1]=1;
    q.push(1);
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            if(dis[edge[i].v]>dis[u]+edge[i].m)
            {
                dis[edge[i].v]=dis[u]+edge[i].m;
                if(vis[edge[i].v]==0)
                {
                    q.push(edge[i].v);
                    vis[edge[i].v]=1;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int u,v,w,t;
    cin>>t;
    for(int kk=1;kk<=t;kk++)
    {
        memset(head,-1,sizeof(head));
        memset(vv,0,sizeof(vv));
        memset(dis,0x3f3f3f3f,sizeof(dis));
        cin>>n>>m>>c;
        k=1;
        for(int i=1;i<=n;i++)//i在第u层
        {
            cin>>u;
            lay[i]=u;
            vv[u]=1;
        }

        for(int i=1;i<n;i++)//相邻的层之间成本为c
        {
            if(vv[i]&&vv[i+1])
            {
                add(n+i,n+i+1,c);
                add(n+i+1,n+i,c);
            }
        }

        for(int i=1;i<=n;i++)
        {
            add(n+lay[i],i,0);//层内0成本
            if(lay[i]>1)//点到临近的层见成本为c
                add(i,n+lay[i]-1,c);
            if(lay[i]<n)
                add(i,n+lay[i]+1,c);
        }

        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w;//点与点间
            add(u,v,w);
            add(v,u,w);
        }
        
        spfa();
        cout<<"Case #"<<kk<<": ";
        if(dis[n]==0x3f3f3f3f)cout<<"-1"<<endl;
        else cout<<dis[n]<<endl;
    }
    return 0;
}

17.ORZ

18.https://cn.vjudge.net/problem/HDU-4370

题目链接:https://cn.vjudge.net/problem/HDU-4370
题目大意:给你一个n*n的矩阵c,让你构造一个满足1,2,3三条条件的矩阵x,求x中元素和的最小值;
解题思路:对于矩阵x
由X 12+X 13+…X 1n=1 可知点1的出度为1
由X 1n+X 2n+…X n-1n=1可知点n的入度为1
由for each i (1kuangbin的博客
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,mp[330][330],vis[330],dis[330];

void spfa(int start)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    queue<int>q;
    for(int i=1; i<=n; i++)//为判断闭环,将其他点都入队
    {
        dis[i]=mp[start][i];
        if(mp[start][i]!=0x3f3f3f3f)
        {
            q.push(i);
            vis[i]=1;
        }
    }
    dis[start]=0x3f3f3f3f;//起始点不入队
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=1; i<=n; i++)
        {
            if(dis[i]>dis[u]+mp[u][i])
            {
                dis[i]=dis[u]+mp[u][i];
                if(!vis[i])
                {
                    vis[i]=1;
                    q.push(i);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        memset(mp,0x3f3f3f3f,sizeof(mp));
        int ans=0x3f3f3f3f;
        int l=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                cin>>mp[i][j];
            }
            mp[i][i]=0;
        }
        spfa(1);
        ans=min(ans,dis[n]);
        l+=dis[1];
        spfa(n);
        l+=dis[n];
        ans=min(ans,l);
        cout<<ans<<endl;
    }
    return 0;
}

19.Layout

题目链接:https://cn.vjudge.net/problem/POJ-3169
题目大意:两头牛之间的距离不能大于给定值,也不能小于给定值,问1到n最长可以间隔的距离
解题思路:差分约束
a-b<=c||b-a<=c 大-小<=c ,有向边(小,大)=c a-b>=c||b-a>=c b-a<=-c||b-a<=-c 大-小>=c,小-大<=-c,有向边(大,小)=-c 代码 [c] #include <iostream> #include <cstring> #include <queue> using namespace std; int n,ml,md; int mp[1100][1100]; int dis[1100],vis[1100],cnt[1100]; void spfa() { memset(vis,0,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis)); memset(cnt,0,sizeof(cnt)); queue<int>q; q.push(1); vis[1]=1; dis[1]=0; cnt[1]++; while(!q.empty()) { int u=q.front(); vis[u]=0; q.pop(); for(int i=1;i<=n;i++) { if(dis[i]>dis[u]+mp[u][i]) { dis[i]=dis[u]+mp[u][i]; if(!vis[i]&&cnt[i]<=n) { vis[i]=1; q.push(i); cnt[i]++; } } } } } int main() { ios::sync_with_stdio(false); int a,b,c; memset(mp,0x3f3f3f3f,sizeof(mp)); for(int i=0;i<=n;i++) { mp[i][i]=0; } cin>>n>>ml>>md; for(int i=0;i<ml;i++) { cin>>a>>b>>c; if(a>b)swap(a,b); mp[a][b]=c; } for(int i=0;i<md;i++) { cin>>a>>b>>c; if(a>b)swap(a,b); mp[b][a]=-c; } spfa(); if(dis[n]==0x3f3f3f3f)cout<<"-2"<<endl; else if(cnt[n]>n)cout<<"-1"<<endl; else cout<<dis[n]<<endl; return 0; } [/c]

1 thought on “专题四 最短路练习”

发表评论

电子邮件地址不会被公开。 必填项已用*标注