http://acm.timus.ru/problem.aspx?space=1&num=1314
最短路 根据罪犯的逃跑线路 从起点求一次最短路 起点距离为0 然后从最后一个点求一次最短路 起点距离是K-1
然后比较两个最短路相等的点
发现一个小的地方需要注意 定义一个数组 dist1[N] ，sizeof（dist1）的大小就是数组的大小
但是如果将数组进行函数调用时 传过去了一个数组指针 dist[] 这时候 sizeof(dist) 为指针占内存大小 需要注意
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include <iomanip>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
//priority_queue<int,vector<int>,greater<int> >qt;
const int N=40005;
const int M=100005;
int head[N],I;
struct node
{
int j,next;
}side[M];
int dist1[N],dist2[N];
vector<int>ans;
void add(int i,int j)
{
side[I].j=j;
side[I].next=head[i];
head[i]=I++;
}
void spfa(int s,int d,int dist[])
{
bool in[N];
memset(in,false,sizeof(in));
memset(dist,-1,sizeof(dist1));
queue<int>qt;
qt.push(s);
in[s]=true;
dist[s]=d;
while(!qt.empty())
{
int x=qt.front();qt.pop();
in[x]=false;
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(dist[j]==-1||dist[j]>dist[x]+1)
{
dist[j]=dist[x]+1;
if(!in[j])
{
in[j]=true;
qt.push(j);
}
}
}
}
}
int main()
{
//freopen("data.in","r",stdin);
int n;
while(cin>>n)
{
ans.clear();
memset(head,-1,sizeof(head));
I=0;
int m;
int pre,k;
while(n--)
{
pre=-1;
cin>>m;
while(m--)
{
cin>>k;
if(pre!=-1)
{
add(pre,k);
add(k,pre);
}
pre=k;
}
}
cin>>m;
int tmp=m-1;
cin>>k;
spfa(k,0,dist1);
while(--m)
{
cin>>k;
}
spfa(k,tmp,dist2);
for(int i=1;i<N;++i)
if(head[i]!=-1&&dist1[i]==dist2[i])
ans.push_back(i);
sort(ans.begin(),ans.end());
for(unsigned int i=0;i<ans.size();++i)
cout<<ans[i]<<endl;
}
}
