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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:求助啊啊啊,用dijkstra做WA到底,找了能找的测试数据均通过了啊,附代码(有注释啊啊)

Posted by yaoguang2034 at 2020-04-06 12:07:45 on Problem 1062
In Reply To:求助啊啊啊,用dijkstra做WA到底,找了能找的测试数据均通过了啊,附代码(有注释啊啊) Posted by:jus_one at 2015-03-04 21:55:59
> /*
> 1。与酋长等级差超过m直接排除
> 2.分别以j(2...n)为源点,1为终点执行dijkstra(执行前先排除等级不在范围的点)
> 3.取得所有结果的最小值
> */
> #include<cstdio>
> #include<cstring>
> #define INF 0x03f3f3f3f
> const int N=101;
> int dist[N],G[N][N],level[N],money[N];
> bool vis[N];
> int left,right;
> bool under_limit(int l)
> {
>     return  (l>=left&&l<=right);
> }
> int  dijkstra(int s,int n)
> {
>     int i,j,min;
>     vis[s]=true;
>     for(i=1;i<=n;++i){
>         dist[i]=INF;
>     }
>     dist[s]=0;
>     int pre=s;
>     for(i=1;i<n;++i){
>         min=INF;
>         for(j=1;j<=n;++j)//取得最优点pre
>             if(!vis[j]&&dist[j]<min)
>                 min=dist[j],pre=j;
>         for(j=1;j<=n;++j)//更新dist
>             if(vis[j]==0&&(dist[pre]+G[pre][j]<dist[j]))
>                 dist[j]=dist[pre]+G[pre][j];
>         vis[pre]=true;
>     }
>     return dist[1];
> }
> int min(int a,int b){return a<b?a:b;}
> int main()
> {
>     int i,j,n,m,p,l,x,t,v;
>     scanf("%d %d",&m,&n);
>     for(i=0;i<N;++i)
>         for(j=0;j<N;++j)G[i][j]=INF;
>     for(i=1;i<=n;++i){
>         scanf("%d %d %d",&p,&l,&x);
>         level[i]=l,money[i]=p;
>         for(j=0;j<x;++j)
>         {
>             scanf("%d %d",&t,&v);
>             G[t][i]=v;
>         }
>     }
>         int ans=INF;
>         for(i=1;i<=n;++i)
>             if(level[i]-level[1]<=m&&level[i]-level[1]>=-m){/*起点与终点等级相差不大于M*/
>                 if(level[i]<level[1])/*计算得到以j为起点1为终点要求的等级范围*/
>                     left=level[1]-m,right=level[i]+m;
>                 else
>                     left=level[i]-m,right=level[1]+m;
>                 memset(vis,0,sizeof(vis));
>                 for(j=1;j<=n;++j)
>                 {
>                     if(!under_limit(level[j]))/*把不在范围的点标记为已访问,表示不再访问*/
>                         vis[j]=true;
>                 }
>                 ans=min(dijkstra(i,n)+money[i],ans);/**/
>         }
>         printf("%d\n",ans);
>         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