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)

Posted by yc5_yc at 2012-07-07 10:00:27 on Problem 2253
核心:
double Dijk(int a,int b)
{
    for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
    M[a]=0,inq[a]=1;
    for(int I=1;I<N;I++)
    {
        double Minn=100000000;
        int Min;
        for(int i=1;i<=N;i++)
        {
            if(!inq[i] && M[i]<Minn)
            {
                Minn=M[i];
                Min=i;
            }
        }
        inq[Min]=1;
        for(int i=1;i<=N;i++)
            if(!inq[i] && G[Min][i]<100000000)
                if(M[Min]+G[Min][i]<M[i])
                    M[i]=M[Min]+G[Min][i];
    }
    return M[b];
}
这一题用了一个改版,其中M数组记录松弛过程中的一个边,我们可以想到因为以后的每次松弛都会沿用原来松弛的某个边,于是我们可以用一个变量记录松弛中的最大边,最后返回它就行了.
改版:
double Dijk(int a,int b)
{
    for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
    M[a]=0,inq[a]=1;
    double Maxn=0;
    for(int I=1;I<N;I++)
    {
        double Minn=100000000;
        int Min;
        for(int i=1;i<=N;i++)
        {
            if(!inq[i] && M[i]<Minn)
            {
                Minn=M[i];
                Min=i;
            }
        }
        if(Minn>Maxn) Maxn=Minn;
        if(Min==b)
            return Maxn;
        inq[Min]=1;
        for(int i=1;i<=N;i++)
            if(!inq[i] && G[Min][i]<100000000)
                if(G[Min][i]<M[i])
                    M[i]=G[Min][i];
    }
}

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