当前位置:首页 > 数据结构 > L3-014. 周游世界

L3-014. 周游世界

周游世界是件浪漫事,但规划旅行路线就不一定了…… 全世界有成千上万条航线、铁路线、大巴线,令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟,每家公司提供一条线路,然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序,使得对任何给定的起点和终点,可以找出最顺畅的路线。所谓“最顺畅”,首先是指中途经停站最少;如果经停站一样多,则取需要换乘线路次数最少的路线。

输入格式:

输入在第一行给出一个正整数N(<= 100),即联盟公司的数量。接下来有N行,第i行(i=1, ..., N)描述了第i家公司所提供的线路。格式为:

M S[1] S[2] ... S[M]

其中M(<= 100)是经停站的数量,S[i](i=1, ..., M)是经停站的编号(由4位0-9的数字组成)。这里假设每条线路都是简单的一条可以双向运行的链路,并且输入保证是按照正确的经停顺序给出的 —— 也就是说,任意一对相邻的S[i]和S[i+1](i=1, ..., M-1)之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间,每个运营区间只承包给一家公司。环线是有可能存在的,但不会不经停任何中间站点就从出发地回到出发地。当然,不同公司的线路是可能在某些站点有交叉的,这些站点就是客户的换乘点,我们假设任意换乘点涉及的不同公司的线路都不超过5条。

在描述了联盟线路之后,题目将给出一个正整数K(<= 10),随后K行,每行给出一位客户的需求,即始发地的编号和目的地的编号,中间以一空格分隔。

输出格式:

处理每一位客户的需求。如果没有现成的线路可以使其到达目的地,就在一行中输出“Sorry, no line is available.”;如果目的地可达,则首先在一行中输出最顺畅路线的经停站数量(始发地和目的地不包括在内),然后按下列格式给出旅行路线:

Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
......

其中Xi是线路承包公司的编号,Si是经停站的编号。但必须只输出始发地、换乘点和目的地,不能输出中间的经停站。题目保证满足要求的路线是唯一的。

输入样例:

4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013
6666 2001
2004 3001
2222 6666

输出样例:

2
Go by the line of company #3 from 3011 to 3013.
10
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
6
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.

首先 我这里是用了完全图,不推荐,但是比较方便

又 这里会出现环!!没注意 但是用dij草过去了

总的来说 把所有车站都当作点!同一车站内的点相互画边  然后按多条件dij

改天做个spfa的正确方法

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

#define N 100005
struct p
{
    int to,id,val;
}pre[N];

struct pp
{
    int u,cz,hc,id;
    bool operator < (const pp &r) const
    {
        if(cz!=r.cz) return cz>r.cz;
        return hc>r.hc;
    }
};
int n,a[105][105];
vector<p>G[N];
int vis[N],dist[N],hc[N];
priority_queue<pp>q;
void dijkstra(int s,int e)
{
    memset(vis,0,sizeof(vis));
    memset(dist,0x3f,sizeof(dist));///记录跑了多少个站
    memset(pre,-1,sizeof(pre));
    memset(hc,0x3f,sizeof(hc));///记录了换了多少次车
    dist[s]=0;
    hc[s]=0;
    q.push((pp){s,0,0,-1});
    while(!q.empty())
    {
        pp now=q.top();
        q.pop();
        if(vis[now.u]) continue;
        vis[now.u]=1;
        for(int i=0; i<G[now.u].size(); i++)
        {
            p t=G[now.u][i];
            int temp= t.id==now.id ?hc[now.u]:hc[now.u]+1;
            if(dist[t.to]>dist[now.u]+t.val )
            {
                pre[t.to]=(p){now.u,t.id};
                hc[t.to]=temp;
                dist[t.to]=dist[now.u]+t.val;
                q.push((pp){t.to,dist[t.to],hc[t.to],t.id});
            }else if(dist[t.to]==dist[now.u]+t.val&& hc[t.to]>temp){
                pre[t.to]=(p){now.u,t.id};
                hc[t.to]=temp;
                dist[t.to]=dist[now.u]+t.val;
            }
        }
    }
}
int main()
{
    int t,k,q,s,e;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&k);
        for(int j=1; j<=k; j++)
        {
            scanf("%d",&a[i][j]);
        }
        for(int j=1; j<=k; j++)
            for(int l=1; l<=k; l++)
            {
                if(j==l) continue;
                G[a[i][j]].push_back((p){a[i][l],i,abs(j-l)});
            }
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d %d",&s,&e);
        dijkstra(s,e);
        stack<p>sta;
        p k=(p){e,0};
        while(k.to!=-1)
        {
            sta.push(k);
            k=pre[k.to];
        }
        if(dist[e]==0x3f3f3f3f) {
            printf("Sorry, no line is available.\n");
            continue;
        }
        printf("%d\n",dist[e]);
        k=(p){s,sta.top().id};
        sta.pop();
        while(!sta.empty())
        {
            printf("Go by the line of company #%d from %04d to %04d.\n",k.id,k.to,sta.top().to);
            k=sta.top();
            sta.pop();
        }
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=422

发表评论

  •  11111
     发布于 2017-12-23 11:34:43  回复该评论
  • 作者能给解释一下u,cz,id分别代表什么吗
    •  dwh
       发布于 2017-12-25 16:39:44  回复该评论
    • 结合起来是 起点到u时 经过的cz(车站)数 id是当前正在几号线 用来判断是否需要换线

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。