| ||||||||||
| 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