http://acm.timus.ru/problem.aspx?space=1&num=1314
最短路 根據(jù)罪犯的逃跑線路 從起點(diǎn)求一次最短路 起點(diǎn)距離為0 然后從最后一個(gè)點(diǎn)求一次最短路 起點(diǎn)距離是K-1?
然后比較兩個(gè)最短路相等的點(diǎn)
發(fā)現(xiàn)一個(gè)小的地方需要注意 定義一個(gè)數(shù)組 dist1[N] ，sizeof（dist1）的大小就是數(shù)組的大小
但是如果將數(shù)組進(jìn)行函數(shù)調(diào)用時(shí) 傳過(guò)去了一個(gè)數(shù)組指針 dist[] 這時(shí)候 sizeof(dist) 為指針占內(nèi)存大小 需要注意
代碼：
#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;
}
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(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ì)您有幫助就好】元
