Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
应该是djkstra算法有问题,因为题目要求不能经过城镇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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator