7-14 周游世界 (30 分)
#include<bits/stdc++.h> using namespace std; struct node { int station,line,ji_sta,ji_line; node() {} node(int a,int b,int c,int d):station(a),line(b),ji_sta(c),ji_line(d) {} bool operator<(const node&tt)const { if(tt.ji_sta!=ji_sta) { return ji_sta>tt.ji_sta; } return ji_line>tt.ji_line; } } now; struct line { int u,v,w,next; } edge[10010]; int head[234234]; int cnt; void add(int u,int v,int w) { edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; edge[cnt].u = v; edge[cnt].v = u; edge[cnt].w = w; edge[cnt].next = head[v]; head[v] = cnt++; } int l,s; priority_queue<node>o; int line[300][10300],station[300][10300]; int bfs(int S,int E) { int vis[435]; memset(vis,-1,sizeof vis); while(!o.empty())o.pop(); o.push(node(S,-2,0,0)); while(!o.empty()) { now = o.top(); o.pop(); if(now.station==E) { l = now.line; s = now.station; return now.ji_sta; } int u = now.station; for(int i=head[u]; ~i; i=edge[i].next) { s = edge[i].v; l = edge[i].w; if(line[s][l]==-1) { line[s][l] = now.line; station[s][l] = now.station; int k; if(l!=now.line)k = now.ji_line+1; else k = now.ji_line; o.push(node(s,l,now.ji_sta+1,k)); } } } return -1; } int ans_l[10300],ans_s[10300],ans_e[10323]; int main() { int n; cin>>n; cnt =0; memset(head,-1,sizeof head); memset(station,-1,sizeof station); memset(line,-1,sizeof station); for(int i=1; i<=n; i++) { int p,pre ; cin>>p>>pre; for(int j=1; j<=p-1; j++) { int num; cin>>num; add(pre,num,i); pre = num; } } int m; cin>>m; for(int ii=1; ii<=m; ii++) { int S,E,ll,ss; cin>>S>>E; int ans_cnt = bfs(S,E); if(ans_cnt != -1) { printf("%d\n", ans_cnt); if(ans_cnt == 0) { printf("Go by the line of company #%d from %04d to %04d.\n", edge[head[S]].w,S, E); continue; } ans_l[0] = -1; int ans_num = 1; while(s != S) { ans_l[ans_num] = l; ans_s[ans_num] = station[l][s]; ans_e[ans_num++] = s; ll = l; l = line[l][s]; s = station[ll][s]; } ss = S; for(int i = ans_num - 1; i > 0; --i) { if(ans_l[i] != ans_l[i - 1]) { printf("Go by the line of company #%d from %04d to %04d.\n", ans_l[i], ss, ans_e[i]); ss = ans_s[i - 1]; } } } else { printf("Sorry, no line is available.\n"); } } return 0; }