2017-04-10 06:06

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

5

http://ac.jobdu.com/problem.php?pid=1100

``````
#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]);
}
}
}
}

``````
• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答