#include#include<" />

日韩久久久精品,亚洲精品久久久久久久久久久,亚洲欧美一区二区三区国产精品 ,一区二区福利

1434. Buses in Vasyuki

系統(tǒng) 1992 0

http://acm.timus.ru/problem.aspx?space=1&num=1434

將每一條線路 看成一個點(diǎn)? 有共同站點(diǎn)的線路連一條邊 并記錄是那個共同站點(diǎn)? 由于可能有多個共同站點(diǎn)? 為了節(jié)約內(nèi)存 應(yīng)該避免建重邊?

擁有出發(fā)站點(diǎn)的線路可以作為搜索的起點(diǎn) 擁有終點(diǎn)站點(diǎn)的線路可以是搜索的終點(diǎn)? 這樣的話用來搜索起點(diǎn)和終點(diǎn)就有多個了

然后一遍bfs? 最先搜到的終點(diǎn) 為最近? 然后注意記錄路徑

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

#define sint short int

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N=100005;

const int M=2000005;

const int K=1005;

int head[K],I;

struct node

{

    int j,next;

    int k;

}side[M];

bool dist[K];

bool L[K][K];

int f[K],kf[K];

bool nd[K];

vector<int>road;

queue<int>qt;

vector<int>link[N];

void add(int i,int j,int k)

{

    if(L[i][j]==true)

    return ;

    L[i][j]=true;

    side[I].j=j;

    side[I].next=head[i];

    side[I].k=k;

    head[i]=I++;

}

void init(int n,int m)

{

    memset(head,-1,sizeof(head));

    memset(L,false,sizeof(L));

    I=0;

    for(int i=1;i<=m;++i)

    link[i].clear();

    for(int i=1;i<=n;++i)

    {

        int tmp;

        cin>>tmp;

        while(tmp--)

        {

            int k;

            cin>>k;

            for(unsigned j=0;j<link[k].size();++j)

            {

                if(link[k][j]==i)

                break;

                add(link[k][j],i,k);add(i,link[k][j],k);

            }

            link[k].push_back(i);

        }

    }

}

int bfs(int n)

{

    int flag=0;

    while(!qt.empty())

    {

        int x=qt.front();qt.pop();

        if(nd[x]==true)

        {flag=x;break;}

        for(int t=head[x];t!=-1;t=side[t].next)

        {

            int j=side[t].j;

            if(dist[j]==false)

            {

                dist[j]=true;

                f[j]=x;

                kf[j]=side[t].k;

                qt.push(j);

            }

        }

    }

    if(flag)

    {

        int k=flag;

        while(f[k]!=-1)

        {

            road.push_back(kf[k]);

            k=f[k];

        }

    }

    return flag;

}

int main()

{

    //freopen("data.in","r",stdin);

    int n,m;

    cin>>n>>m;

    init(n,m);

    int x1,x2;

    cin>>x1>>x2;

    if(x1==x2)

    {cout<<"0"<<endl;cout<<x1<<endl;return 0;}

    memset(dist,false,sizeof(dist));

    memset(f,-1,sizeof(f));

    memset(nd,false,sizeof(nd));

    for(unsigned int i=0;i<link[x1].size();++i)

    {dist[link[x1][i]]=true;qt.push(link[x1][i]);}

    for(unsigned int i=0;i<link[x2].size();++i)

    {nd[link[x2][i]]=true;}

    if(!bfs(n))

    {cout<<"-1"<<endl;return 0;}

    road.insert(road.begin(),x2);

    cout<<road.size()<<endl;

    cout<<x1;

    for(int i=road.size()-1;i>=0;--i)

    cout<<" "<<road[i];

    cout<<endl;

    return 0;

}


    

1434. Buses in Vasyuki


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 江永县| 通渭县| 尼木县| 永仁县| 望江县| 辽源市| 郑州市| 上高县| 峡江县| 内黄县| 收藏| 大洼县| 西安市| 丹寨县| 洞头县| 富蕴县| 松潘县| 牡丹江市| 慈溪市| 大理市| 偏关县| 凯里市| 阿瓦提县| 饶阳县| 明光市| 邹城市| 榆林市| 仁寿县| 云林县| 定襄县| 临泽县| 张家口市| 安义县| 建始县| 宁德市| 定襄县| 上思县| 汝州市| 嘉峪关市| 合阳县| 崇明县|