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;
}
更多文章、技術(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ì)您有幫助就好】元
