九度OJ上的迪杰斯特拉算法题

Question

九度OJ上的一道题
http://ac.jobdu.com/problem.php?pid=1100
思路是使用迪杰斯特拉算法，结合高精度整数运算
我测试了好多测试用例都没又发现错误
但是提交后现实WA，求大神指明错误，感激不尽啊。。。

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <math.h>
#include <time.h>
#include <map>
#include <algorithm>
#include<memory.h>
#define MAX 0x0fffffff
#define K 100000
using namespace std;



class BigInt
{
public:
    int num[100];
    int n;
    BigInt(string s)
    {
        for(int i=0;i<100;i++)
            num[i] = 0;
        int res = 0;
        int cnt = 0;
        int weight = 1;
        n = 0;
        for(int i=s.size()-1;i>=0;i--)
        {
            res += weight*(s[i]-'0');
            cnt++;
            weight*=10;
            if(cnt==4||i==0)
            {
                num[n++] = res;
                res = 0;
                cnt = 0;
                weight = 1;
            }
        }
    }
    BigInt()
    {
        for(int i=0;i<100;i++)
            num[i] = 0;
        n=0;
    }
    friend const BigInt operator + (const BigInt & bi1,const BigInt & bi2)
    {
        int carry = 0;
        BigInt Res;
        int k =0;
        for(int i=0;i<bi1.n||i<bi2.n;i++)
        {
            int res = bi1.num[i]+bi2.num[i]+carry;
            int remainder = res%10000;
            carry = res/10000;
            Res.num[k++] = remainder;
        }
        if(carry!=0)
        {
            Res.num[k++] = carry;
        }
        Res.n = k;
        return Res;
    }
    friend const BigInt operator * (const BigInt & bi,const int & m)
    {
        int carry = 0;
        BigInt Res;
        int k =0;
        for(int i=0;i<bi.n;i++)
        {
            int res = bi.num[i]*m+carry;
            carry = res/10000;
            Res.num[k++] = res%10000;
        }
        if(carry!=0)
        {
            Res.num[k++] = carry;
        }
        Res.n = k;
        return Res;
    }
    friend const int operator % (const BigInt & bi,const int & m)
    {
        int r = 0;
        for(int i=bi.n-1;i>=0;i--)
        {
            int remainder = (r*10000+bi.num[i])%m;
            r = remainder;
        }
        return r;
    }


    friend const bool operator <(const BigInt & bi1,const BigInt & bi2)
    {
        if(bi1.n<bi2.n)return true;
        else if(bi1.n>bi2.n)return false;
        else
        {
            int carry =0 ;
            int k = 0;
            for(int i=0;i<bi1.n||i<bi2.n;i++)
            {
                int res = bi1.num[i]-bi2.num[i]+carry;
                if(res<0)
                {
                    res+=10000;
                    carry = -1;
                }
                else carry = 0;
            }
            if(carry<0)return true;
            else return false;
        }
    }
    friend const bool operator >(const BigInt & bi1,const BigInt & bi2)
    {
        if(bi1.n>bi2.n)return true;
        else if(bi1.n<bi2.n)return false;
        else
        {
            int carry =0 ;
            int k = 0;
            for(int i=0;i<bi1.n||i<bi2.n;i++)
            {
                int res = bi1.num[i]-bi2.num[i]+carry;
                if(res<0)
                {
                    res+=10000;
                    carry = -1;
                }
                else carry = 0;
            }
            if(carry<0)return false;
            else return true;
        }
    }

};

class Edge
{
public:
    int num;
    BigInt weight;
    Edge(int num,BigInt weight)
    {
        this->num = num;
        this->weight  = weight;
    }
    Edge()
    {
        this->num = -1;
    }
};

vector<vector<Edge> > V(101,vector<Edge>());
vector<bool> Visited(101,false);
void Init()
{
    V.clear();
    Visited.clear();
    V.resize(101,vector<Edge>());
    Visited.resize(101,false);
}

void Output(BigInt bi)
{
    for(int i=bi.n-1;i>=0;i--)
    {
        if(i==bi.n-1)cout<<bi.num[i];
        else printf("%04d",bi.num[i]);
    }
    //cout<<'k';
    cout<<endl; 

}
int main()
{
    freopen("D:\\input.txt","r",stdin);
    int n,m;
    while(cin>>n>>m)
    {
        Init();
        BigInt weight("1");
        vector<BigInt> Dist(n,BigInt());
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            //Output(weight);
            V[a].push_back(Edge(b,weight));
            V[b].push_back(Edge(a,weight));
            weight = weight*2;

        }
        Visited[0] = true;
        Dist[0] = BigInt("0");
        for(int i=0;i<V[0].size();i++)
        {
            Dist[V[0][i].num] = V[0][i].weight;
        }

        int cnt =n;
        cnt--;
        while(cnt--)
        {
            BigInt min_weight("123123123");
            int min_num = -1;
            for(int i=0;i<n;i++)
            {

                if(!Visited[i]&&Dist[i].n!=0&&Dist[i]<min_weight)
                {
                    min_weight = Dist[i];
                    min_num = i;
                }
            }
            //cout<<min_num<<endl;
            if(min_num==-1)
            {
                break;
            }
            Visited[min_num] = true;

            for(int i=0;i<V[min_num].size();i++)
            {
                int target_ind = V[min_num][i].num;
                BigInt target_weight = V[min_num][i].weight;
                if(!Visited[target_ind]&&(Dist[target_ind].n==0||Dist[target_ind]>Dist[min_num]+target_weight))
                {
                    Dist[target_ind] = Dist[min_num]+target_weight;
                }
            }
        }

        for(int i=1;i<n;i++)
        {
            if(Dist[i].n==0)cout<<-1<<endl;
            else 
            {
                if(Dist[i].n>=2)
                {
                    cout<< Dist[i]%K<<endl;
                }
                else
                    Output(Dist[i]);
            }
        }
    }
}

Answer 1

http://blog.csdn.net/bruce128/article/details/7270676