#include#include<" />

欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

1434. Buses in Vasyuki

系統(tǒng) 1915 0

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

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

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

然后一遍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號(hào)聯(lián)系: 360901061

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

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 亚洲午夜小视频 | 狠狠干天天干 | 成人超碰 | 亚洲欧洲日本天天堂在线观看 | 九九热精品视频在线播放 | 日韩精品一区二区三区在线播放 | 亚洲 欧美 中文字幕 | 99国产精品久久久久久久成人热 | 国产91高清在线 | 91香焦视频 | 日韩欧美亚洲 | 最新中文字幕在线 | 国产a精品 | 色中文网 | 天天摸天天射 | 黑人群姣中国妞在线观看 | 男生插女生视频免费 | 日本不良网站 | 国产成人免费无庶挡视频 | 免费一二区 | 亚洲精品中文字幕在线观看 | 国产在线91精品入口首页 | 欧美国产免费 | 亚洲第一国产 | 青草青草久热精品视频在线网站 | 国产欧美视频一区二区三区 | 热伊人99re久久精品最新地 | yw在线播放 | 国内精品视频 | 久久久精品视频免费观看 | 久爱网| 亚洲第一视频 | 好吊日在线观看 | 波多野结衣亚洲 | 国产深夜福利视频在线 | 国产精品久久久久久婷婷天堂 | 无码免费人妻A片AAA毛 | 杏导航aⅴ福利网站 | 国产精品久久福利新婚之夜 | 日本一区二区不卡 | 热er99久久6国产精品免费 |