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

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

Posted by jus_one at 2015-03-04 21:55:59 on Problem 1062
/*
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