HDU 2377 Bus Pass prime 의 사상 + spfa

제목: nz 개 구역 이 있 고 한 버스 노선 은 nr 라인 을 지나 고 구역 과 구역 사이 에 공공 변 이 있 으 며 연결 되 어 있 음 을 나타 낸다. 거 리 는 1 이다. 어느 점 에서 버스 노선 의 모든 점 까지 의 거리 가 가장 길 고 가장 작은 지 물 어보 자.
생각: 폭력 을 생각 하기 시 작 했 습 니 다. 분명히 시간 이 허락 되 지 않 았 습 니 다. 그러면 여기 서 prime 알고리즘 을 사용 한 작은 사상 인 A, B 집합, A 집합 은 모든 점 에서 B 집합 까지 모든 점 에서 최소 치 를 low 배열 에 저장 합 니 다. 그러면 지금 은 버스 노선 을 A 집합 으로 보고 나머지 점 은 B 집합 으로 봐 야 합 니 다. 그러면 우 리 는 B 집합 중의 모든 점 을 찾 아야 합 니 다.A 집합 거리 (B 집합 에서 A 집합 거리: B 집합 중의 점 u 에서 A 집합 중의 모든 점 거리 중 거리 가 가장 큰 것) 에 이 르 러 이 거 리 를 업데이트 한 후 가장 작은 것 을 찾 으 면 된다.생각해 보면 납득 이 간다.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int nodes=10000;
const int edges=200000+500;
struct node
{
	int v,next,w;
}e[edges];
int head[nodes],cnt,max_dis[nodes];
int nz,nr;
void Init()
{
	memset(head,-1,sizeof(head));
	cnt=0;
	memset(max_dis,-1,sizeof(max_dis));
}
void add(int a,int b,int c)
{
	e[cnt].v=b;
	e[cnt].w=c;
	e[cnt].next=head[a];
	head[a]=cnt++;
}
void spfa(int s)
{
	queue<int>q;
	while(!q.empty()) q.pop();
	int dis[nodes],vis[nodes];
	for(int i=1;i<=9999;i++)
	{
		dis[i]=inf;
		vis[i]=0;
	} 
	vis[s]=1;
	dis[s]=0;
	if(max_dis[s]==-1)
	max_dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i+1;i=e[i].next)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				if(max_dis[v]<dis[v])
				max_dis[v]=dis[v];
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	int test;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d%d",&nz,&nr);
		Init();
		for(int i=1;i<=nz;i++)
		{
			int a,num;
			scanf("%d%d",&a,&num);
			while(num--)
			{
				int b;
				scanf("%d",&b);
				add(a,b,1);
				add(b,a,1);
			}
		}
		for(int i=1;i<=nr;i++)
		{
			int num;
			scanf("%d",&num);
			while(num--)
			{
				int a;
				scanf("%d",&a);
				spfa(a);
			}
		}
		int pos,val=inf;
		for(int i=1;i<=9999;i++)
		{
			if(max_dis[i]<val&&max_dis[i]!=-1)
			{
				val=max_dis[i];
				pos=i;
			}
		}
		printf("%d %d
",val+1,pos);
	}
	return 0;
}