Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

应该是djkstra算法有问题,因为题目要求不能经过城镇

Posted by 00648274 at 2007-12-16 02:07:17 on Problem 1161
In Reply To:一直WA,不知错在哪里帮忙看看! Posted by:rdstwww at 2007-07-21 13:57:11
> #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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator