#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <string>
#include <cmath>
#include <cstdlib>
#include "heap.h"
#include "list.h"
#include "matrix.h"
#define INF 0x0fffffff
Net_Modu dijkstra(const Net_Modu &Net)
{
Net_Modu net(Net,3);
Vec tmp_dist;
Vec tmp_index;
Mat dist_sum;
int edge_num=net.mat.size();
int ver_num=net.mat[edge_num-1][0];
vector<Edge> edge(edge_num+1);
for(int i=0;i<edge_num;i++)
{
int from,to,weight;
from=net.mat[i][0];
to=net.mat[i][1];
weight=net.mat[i][2];
edge[from].insert(to,weight);
}
for(int i=1;i<=ver_num;i++)
{
PairingHeap heap(ver_num);
vector<bool> visited(ver_num+1);
vector<double> dist(ver_num+1);
for(int j=1;j<=ver_num;j++)
heap.insert(j,INF);
heap.decrease_key(i,0);
while(!heap.is_empty())
{
double key=heap.find_min();
double flag=heap.find_minpos();
while(visited[flag]&&!heap.is_empty())
{
dist[flag]=key;
heap.delete_min();
key=heap.find_min();
flag=heap.find_minpos();
}
if(heap.is_empty())
break;
visited[flag]=true;
edge[flag].repos();
while(!edge[flag].is_rear())
{
heap.decrease_key(edge[flag]->to,key+edge[flag]->w);
edge[flag]++;
}
}
double sum=0;
for(int k=1;k<=ver_num;k++)
if(k!=i)
sum+=1/dist[k];
tmp_dist.push_back(sum);
tmp_index.push_back(i);
}
dist_sum.push_back(tmp_index);
dist_sum.push_back(tmp_dist);
Net_Modu temp(dist_sum);
quick_sort(temp,0,ver_num-1);
return temp;
}
#ifndef _HYBRID_CPP_
int main(int argc, char **argv)
{
if (3 != argc)
{
cerr << "Usage:" << endl;
cerr << " " << argv[0] << " <fn_netII> <fn_distI>" << endl;
exit(1);
}
char *fn_net = argv[1];
char *fn_dist = argv[2];
Net_Modu net_mat(fn_net,3);
Net_Modu result(dijkstra(net_mat));
ofstream out_file(fn_dist, ios::out);
out_file<<result;
out_file.close();
return 0;
}
#endif
