#include "iostream"
#include "algorithm"
#include "string"
#include "cmath"
using namespace std;
#define MAX 9999999
int m,n,l;
int graph[4510][4510];
int pt[2010][2510],cus[310];
int vis[4510],dis[4510];
int tmp[2010];
int max=0;
dijstra(int begin,int n)
{
	int i,j,edge,visited;
	for(i=1;i<=n;i++)vis[i]=0;
	vis[begin]=1;
	for(i=1;i<=n;i++)dis[i]=graph[begin][i];
	dis[begin]=0;
	while(1){
		edge=MAX;
		for(i=1;i<=n;i++)
			if(vis[i]==0 && dis[i]<edge){
				edge=dis[i];
				visited=i;
			}
		if(edge==MAX)break;
		     vis[visited]=1;
		for(i=1;i<=n;i++)
			if(vis[i]==0 && dis[i]>edge+graph[visited][i])dis[i]=edge+graph[visited][i];
	}
}
int judge(int p,int q)		//判断两个区域是否相邻
{

	int i,j,x=pt[p][0],y=pt[q][0],tmp1,tmp2;
	if(p==q)return 0;
	for(i=1;i<=x;i++)
		for(j=1;j<=y;j++){
			tmp1=(i==x)?1:i+1;
			tmp2=(j==y)?1:j+1;
			if(pt[p][i]==pt[q][j] && pt[p][tmp1]==pt[q][tmp2]) return 1;
			if(pt[p][i]==pt[q][tmp2] && pt[p][tmp1]==pt[q][j]) return 1;
			}
	return 0;
}
int main()
{
	int i,j,k;
	cin>>m>>n>>l;
	for(i=1;i<=l;i++)
		cin>>cus[i];
	for(i=1;i<=m;i++){
		cin>>pt[i][0];
		for(j=1;j<=pt[i][0];j++)
			cin>>pt[i][j];
	}
	for(i=1;i<=l+m;i++)
		for(j=1;j<=l+m;j++)
			graph[i][j]=MAX;
	for(i=1;i<=m;i++)			//将区域i和构成它的的顶点j的边置0
		for(j=1;j<=pt[i][0];j++)
			for(k=1;k<=l;k++)
				if(cus[k]==pt[i][j])graph[k][i+l]=graph[i+l][k]=0;
	for(i=1;i<m;i++)			//将区域i和与它相邻的区域j的边置1
		for(j=i+1;j<=m ;j++)
			if(judge(i,j))graph[i+l][j+l]=graph[j+l][i+l]=1;
	for(i=1;i<=l;i++){
		dijstra(i,m+l);
		for(j=l+1;j<=m+l;j++)
			tmp[j]+=dis[j];
	}
	for(i=l+1,max=MAX;i<=l+m;i++){
		if(max>tmp[i])max=tmp[i];
	}
	cout<<max<<endl;
	return 0;
}

• 应该是djkstra算法有问题，因为题目要求不能经过城镇 (1868) 00648274 2007-12-16 02:07:17