Cod sursa(job #5217)

Utilizator SpiriSpiridon Alexandru Spiri Data 11 ianuarie 2007 03:00:28
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <fstream>
using namespace std;
#define MAX 10001
#define INF 32000

int a[MAX][MAX], n, m, sursa; 
int d[MAX]; // distanta minima fata de sursa
int s[MAX]; // sir caracteristic
int hsize; // adancimea heapului
int pos[MAX]; // pos[i] = j - pozitia in heap a nodului i este j
int h[MAX]; // h retine nodurile dar heapul este consctuit in functie de distanta fata de sursa
int t;
int d2[MAX];

ifstream fin ("distante.in");
ofstream fout ("distante.out");

void Dijkstra();
void BuildHeap();
void InsertHeap(int nod);
int ExtrageMin();
void RebuildHeap(int i);
void MoveUp(int nod);

int main()
{
    fin >> t;
    for ( int k = 1; k <= t; k++ )
    {
        fin >> n >> m >> sursa;
        for ( int j = 1; j <= n; j++ )
        {
            fin >> d2[j];
            d[j] = INF;
            s[j] = 0;
            for ( int j1 = 1; j1 <= n; j1++ ) a[j][j1] = 0;
        }
        int v1,v2,c;
        for ( int i = 1; i <= m; i++ )
        {
            fin >> v1 >> v2 >> c;
            a[v1][v2] = c;
            a[v2][v1] = c;
        }   
        Dijkstra();
        bool k = true;
        for ( int i = 1; i <= n; i++ )
        {
            if ( d[i] != d2[i] )
            {
                 fout << "NU\n";
                 k = false;
                 break;
            }
        }
        if ( k == true )
        {
             fout << "DA\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}

void Dijkstra()
{
     int u = 0;
     BuildHeap();
     
     while ( hsize )
     {
           u = ExtrageMin();
           s[u] = 0;
           for ( int i = 1; i <= n; i++ )
           {
               if ( a[u][i] )
               {
                    if ( d[i] > d[u] + a[u][i] )
                    {
                         d[i] = d[u] + a[u][i];
                         if ( s[i] == 1 )
                         {
                             MoveUp(i);
                         }
                         else
                         {
                             InsertHeap(i);
                             s[i] = 1;
                         }
                    }
               }
           }
     }
}

void BuildHeap()
{
  /*   for ( int i = 1; i <= n; i++ )
     {
         d[i] = INF;
     }*/
     d[sursa] = 0;
     for ( int i = 1; i <= n; i++ )
     {
         if ( a[sursa][i] )
         {
              d[i] = a[sursa][i];
              InsertHeap(i);
              s[i] = 1;
         }
     }
}

void InsertHeap(int nod)
{
     int son = 0;
     int parent = 0;
     son = ++hsize;
     parent = son/2;
     while ( parent && d[h[parent]] > d[h[son]] )
     {
           h[son] = h[parent];
           pos[h[son]] = son;
           son = parent;
           parent = son/2;  
     }
     h[son] = nod;
     pos[nod] = son;
}

int ExtrageMin()
{
    int min = h[1];
    h[1] = h[hsize--];
    RebuildHeap(1);
    return min;
}

void RebuildHeap(int i)
{
     int val = h[i];
     int son = 0;
     int parent = 0;
     parent = i;
     son = 2*parent;
     
     while( son <= hsize )
     {
            if ( son < hsize )
            {
                 if ( d[h[son+1]] < d[h[son]] ) son++;
            }
            if ( d[val] > d[h[son]] )
            {
                 h[parent] = h[son];
                 pos[h[parent]] = parent;
                 parent = son;
                 son = parent*2;
            }
            else break;
     }
     h[parent] = val;
     pos[h[parent]] = parent;
}

void MoveUp(int nod)
{
     int son = 0;
     int parent = 0;
     son = pos[nod];
     parent = son/2;
     while ( parent && d[h[parent]] > d[nod] )
     {
           h[son] = h[parent];
           pos[h[son]] = son;
           son = parent;
           parent = son/2;
     }
     h[son] = nod;
     pos[h[son]] = son;
}