PTA-周游世界

解题思路

单源最短路,首先建图的时候将同一家公司内的任意两点间连一条边,边权为两点之间的距离(途径站数量)。跑最短路时用两个参数,第一参数是途径站数量,第二参数是步数,由于同一个公司间的任意两点间都有直接的通路,所以步数就是换乘的数量。用pre数组记录一下路径即可。
注意不要要在关了流同步的时候混用cout和scanf,挑了一个小时才发现emmm

参考代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int head[11010];
int cnt;
struct node
{
    int v,com,w,nxt;
}edge[1000010];

void addedge(int u,int v,int c,int w)
{
    edge[cnt].v=v;
    edge[cnt].com=c;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}

void spfa(int s,int e)
{
    int v[10010],dis[10010][2],pre[10010][2],pos,aa[10010][2],top=0;
    queue<int>q;
    for(int i=0;i<10000;i++)
    {
        v[i]=0;
        dis[i][0]=dis[i][1]=1e9+7;
        pre[i][0]=-1;
    }
    dis[s][0]=dis[s][1]=0;
    q.push(s);
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        v[s]=0;
        for(int i=head[s];i!=-1;i=edge[i].nxt)
        {
            pos=edge[i].v;
            if(dis[pos][0]>dis[s][0]+edge[i].w)
            {
                dis[pos][0]=dis[s][0]+edge[i].w;
                dis[pos][1]=dis[s][1]+1;
                pre[pos][0]=s;
                pre[pos][1]=edge[i].com;
                if(v[pos]==0)
                {
                    v[pos]=1;
                    q.push(pos);
                }

            }
            else if(dis[pos][0]==dis[s][0]+edge[i].w&&dis[pos][1]>dis[s][1]+1)      //中转站数量更新
            {
                dis[pos][1]=dis[s][1]+1;
                pre[pos][0]=s;
                pre[pos][1]=edge[i].com;
                if(v[pos]==0)
                {
                    v[pos]=1;
                    q.push(pos);
                }
            }
        }
    }
    if(dis[e][0]==1000000007)
    {
        printf("Sorry, no line is available.\n");
    }
    else
    {
        cout<<dis[e][0]<<endl;
        aa[top][0]=e;
        while(pre[e][0]!=-1)
        {
            top++;
            aa[top][1]=pre[e][1];
            e=pre[e][0];
            aa[top][0]=e;
        }
        for(int i=top;i>=1;i--)
        {
            printf("Go by the line of company #%d from %04d to %04d.\n",aa[i][1],aa[i][0],aa[i-1][0]);
        }
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    int a[110];
    cnt=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int m;
        cin>>m;
        for(int j=0;j<m;j++)
        {
            cin>>a[j];
        }
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<m;k++)
            {
                if(j==k)
                    continue;
                addedge(a[j],a[k],i,abs(j-k));
            }
        }
    }
    int kk;
    cin>>kk;
    int u,v;
    for(int i=0;i<kk;i++)
    {
        cin>>u>>v;
        spfa(u,v);
    }
    return 0;
}

发表评论

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