Paste code

#include <iostream>
#include <ctime>
using namespace std;
clock_t e,ee;
const int inf=1000000000,nn=1010;

int x[3][nn*(nn-1)],df[nn][nn],ras[nn],pred[nn],pytb[nn],q=0,ii=0,n,t,l1,l2;
bool v[nn];

int parent(int i)
{return i/2;}

int left(int i)
{return i*2;}

int right(int i)
{return i*2+1;}

int up(int k)
{
 int l,r,h=k;
 l=left(k);
 r=right(k);
 if(l<=ii && x[2][l]<x[2][k]) h=l;
 if(r<=ii && x[2][r]<x[2][h]) h=r;
 if(h!=k)
 {
  t=x[2][k];
  x[2][k]=x[2][h];
  x[2][h]=t;
  t=x[1][k];
  x[1][k]=x[1][h];
  x[1][h]=t;
  t=x[0][k];
  x[0][k]=x[0][h];
  x[0][h]=t;
  up(h);
 }
 return 0;
}

int del(int i)
{
 x[0][i]=x[0][ii];
 x[1][i]=x[1][ii];
 x[2][i]=x[2][ii];
 x[2][ii]=inf;
 ii--;
 up(i);
 return 0;
}

int down(int l)
{
 int h=parent(l);
 if(x[2][h]>x[2][l])
 {
  t=x[2][l];
  x[2][l]=x[2][h];
  x[2][h]=t;
  t=x[1][l];
  x[1][l]=x[1][h];
  x[1][h]=t;
  t=x[0][l];
  x[0][l]=x[0][h];
  x[0][h]=t;
  if(h>1)down(h);
 }
 return 0;
}

int Dijkstra(int k)
{
 v[k]=1;
 q++;
 for(int i=1;i<=ii;i++)
  if(v[x[1][i]]!=0)
   del(i);
 for(int i=1;i<=n;i++)
  if(df[k][i]!=-inf && k!=i)
  {
   if(v[i]==0)
   {
    ii++;
    x[0][ii]=k;
    x[1][ii]=i;
    x[2][ii]=df[k][i];
    if(ii>1)down(ii);
   }
   if(ras[i]>ras[k]+df[k][i])
   {
    pred[i]=k;
    ras[i]=ras[k]+df[k][i];
   }
  }
 for(int i=1;i<=ii;i++)
  if(v[x[1][i]]!=0)
   del(i);
 if(ii>0)Dijkstra(x[1][1]);
 return 0;
}

int main()
{
 e=clock();
 int i,p0,p1,p2,m;
 freopen("in.txt","r",stdin);
 //freopen("out.txt","w",stdout);
 cin>>n>>m>>l1>>l2;
 for(i=0;i<=n;i++)
 {
  v[i]=0;
  ras[i]=inf;
  pred[i]=inf;
  for(int j=0;j<=n;j++)df[i][j]=-inf;
 }
 for(i=0;i<m;i++)
 {
  cin>>p0>>p1>>p2;
  df[p0][p1]=p2;
 }
 ras[l1]=0;
 pred[l1]=l1;
 Dijkstra(l1);
 int h=l2;
 pred[l1]=l1;
 pytb[0]=l2;
 ii=1;
 while(h!=l1)
 {
  pytb[ii]=pred[h];
  if(pred[h]==inf)
  {
   h=l1;
   ii=inf;
   cout<<" Net pyti "<<endl;
   break;
  }
  ii++;
  h=pred[h];
 }
 for(i=ii-1;i>=0 && ii!=inf ;i--)cout<<pytb[i]<<" ("<<ras[pytb[i]]<<") "<<endl;
 ee=clock();
 cout<<" time "<<ee-e<<endl;
 return 0;
}