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)? 這樣的話用來搜索起點(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號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
