那个人派出的队伍的行走的路径一定前半程是重合的，后半程分叉开来。
于是预处理每个点离1号点的最短路，到最近的铁的最短路，到最近的煤的最短路。（三次BFS / SPFA）然后枚举分岔点，尝试更新答案即可。
#include#include #include #include using namespace std;typedef long long ll;queue q;int v[1000010],first[100010],next[1000010],en;ll ans=2147483647ll;void AddEdge(int U,int V){ v[++en]=V; next[en]=first[U]; first[U]=en;}int n,m,K,a[100010],b[100010],dis1[100010],dis2[100010],dis3[100010],eu[1000010],ev[1000010],es;bool inq[100010];void spfa1(int dis[]){ memset(dis,0x7f,sizeof(int)*100010); memset(inq,0,sizeof(inq)); for(int i=1;i<=m;++i){ dis[a[i]]=0; q.push(a[i]); inq[a[i]]=1; } while(!q.empty()) { int U=q.front(); for(int i=first[U];i;i=next[i]) if(dis[v[i]]>dis[U]+1) { dis[v[i]]=dis[U]+1; if(!inq[v[i]]) { q.push(v[i]); inq[v[i]]=1; } } q.pop(); inq[U]=0; }}void spfa2(int dis[]){ memset(dis,0x7f,sizeof(int)*100010); memset(inq,0,sizeof(inq)); for(int i=1;i<=K;++i){ dis[b[i]]=0; q.push(b[i]); inq[b[i]]=1; } while(!q.empty()) { int U=q.front(); for(int i=first[U];i;i=next[i]) if(dis[v[i]]>dis[U]+1) { dis[v[i]]=dis[U]+1; if(!inq[v[i]]) { q.push(v[i]); inq[v[i]]=1; } } q.pop(); inq[U]=0; }}void spfa3(int dis[]){ memset(dis,0x7f,sizeof(int)*100010); memset(inq,0,sizeof(inq)); dis[1]=0; q.push(1); inq[1]=1; while(!q.empty()) { int U=q.front(); for(int i=first[U];i;i=next[i]) if(dis[v[i]]>dis[U]+1) { dis[v[i]]=dis[U]+1; if(!inq[v[i]]) { q.push(v[i]); inq[v[i]]=1; } } q.pop(); inq[U]=0; }}int main(){// freopen("i.in","r",stdin); scanf("%d%d%d",&n,&m,&K); for(int i=1;i<=m;++i){ scanf("%d",&a[i]); } for(int i=1;i<=K;++i){ scanf("%d",&b[i]); } int x,y; for(int i=1;i<=n;++i){ scanf("%d",&x); for(int j=1;j<=x;++j){ scanf("%d",&y); AddEdge(y,i); eu[++es]=i; ev[es]=y; } } spfa1(dis1); spfa2(dis2); memset(first,0,sizeof(first)); memset(next,0,sizeof(next)); memset(v,0,sizeof(v)); en=0; for(int i=1;i<=es;++i){ AddEdge(eu[i],ev[i]); } spfa3(dis3); for(int i=1;i<=n;++i){ ans=min(ans,(ll)dis3[i]+(ll)dis1[i]+(ll)dis2[i]); } if(ans<=2000000000ll){ printf("%d\n",(int)ans); } else{ puts("impossible"); } return 0;}