POJ 2449 A* search K shortest path

First real C++ program

#include<iostream>

#include<fstream>

using namespace std;

int n,m,s,t,k,size;

int l[1001],l2[1001],her[1001],time[1001];

bool used[1001];

fstream fin;

int a,b,r;

struct edge{

    int v,l,t;

};

struct key{

int v,value;

};

edge map[1001][1001],map2[1001][1001];

key data[1001],tmp;

void ready()

{

fin>>n>>m;

   for (int i=1;i<=m;i++)

   {  

  fin>>a>>b>>r;

  l[a]++;

      map[a][l[a]].v=b;

      map[a][l[a]].l=r;

      l2[b]++;

      map2[b][l2[b]].v=a;

      map2[b][l2[b]].l=r;

   }

   fin>>s>>t>>k;

   if (s==t) k++;

}

void dijkstra()

{ int z;

   for (int i=1;i<=n;i++)

her[i]=1000000;

   her[t]=0;

   for (int i=1;i<=n;i++)

   {

  int min=1000000;

  for (int j=1;j<=n;j++)

    if ((!used[j]) && (her[j]<min))

{

min=her[j];

z=j;

  }

used[z]=true;

for (int j=1;j<=l2[z];j++)

{

   if (her[z]+map2[z][j].l<her[map2[z][j].v])

            her[map2[z][j].v]=her[z]+map2[z][j].l;

}

   }

}

void push(int v,int i)

{    int tmp1;

     key temp;

    size++;

data[size].v=map[v][i].v;

data[size].value=tmp.value+map[v][i].l;

tmp1=size;

while (tmp1 > 1)

{

if (data[tmp1 >> 1].value+her[data[tmp1>>1].v]<data[tmp1].value+her[map[v][i].v]) break;

temp=data[tmp1];

data[tmp1]=data[tmp1 >> 1];

data[tmp1 >> 1]=temp;

        tmp1= tmp1 >> 1;

}

}

void del()

{   key temp;

temp=data[size];

data[size]=data[1];

data[1]=temp;

size--;

int i = 1;

while ((i << 1) <= size)

{

int j;

j = i << 1;

if ((j < size) && (data[j + 1].value+her[data[j+1].v]< data[j].value+her[data[j].v])) j++;

if (data[i].value+her[data[i].v]< data[j].value+her[data[j].v]) break;

temp=data[i];

data[i]=data[j];

data[j]=temp;

i = j;

}

}

int a_star()

{ 

if( her[s]==1000000 ) return -1;

data[1].v=s;

data[1].value=0;

  time[s]=0;

  size=1;

  

  while (size>0) {

    time[data[1].v]++;

 if (time[t]==k)

 return data[1].value;

 

      tmp=data[1];

 del();

 if (time[data[1].v]>k) continue;

 for (int e=1;e<=l[tmp.v];e++)

 {push(tmp.v,e);                           

  }

  }

return -1;

}

int main()

{

 fin.open("c:\\test.txt");

ready(); 

 dijkstra();

 int ans;

 ans=a_star();

 cout<<ans;  

 fin.close();

}