Cod sursa(job #1449977)

Utilizator Za_Flafi_Uanmda mda Za_Flafi_Uan Data 11 iunie 2015 09:20:38
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<iostream>
#include<fstream>
#include<limits.h>
#define MAX 20000
using namespace std;
ifstream f1("distante.in"); ofstream f2("distante.out");

int T,n,m,src,dist[MAX],noob[MAX],graph[MAX][MAX];
bool sptSet[MAX];

void readDatas()
{
  int i,x,y,c;
  f1>>n>>m>>src;
  for(i = 1; i <= n; i++) f1>>noob[i];
  for(i = 1; i <= m; i++)
   {
     f1>>x>>y>>c;
     graph[x][y] = graph[y][x] = c;
   }
}

int minDistance()
{
  int min = INT_MAX, min_index,v;
  for (v = 1; v <= n; v++)
    if (sptSet[v] == false && dist[v] <= min)
      {
        min = dist[v];
        min_index = v;
      }
  return min_index;
}

void runDijkstra()
{
  for (int i = 1; i <= n; i++)
   {
     dist[i] = INT_MAX;
     sptSet[i] = false;
   }
  dist[src] = 0;
  for (int i = 1; i < n; i++)
     {
       int u = minDistance();
       sptSet[u] = true;
       for (int v = 1; v <= n; v++)
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v])
         dist[v] = dist[u] + graph[u][v];
     }
}

void checkData()
{
  bool equal = true;
  for(int i = 1 ; i <= n; i++)
    if(dist[i] != noob[i]) equal = false;
  if(!equal) f2<<"NU"<<'\n';
  else f2<<"DA"<<'\n';
}

int main()
{
  f1>>T;
  for(int i = 1; i <= T; i++)
   {
     readDatas();
     runDijkstra();
     checkData();
   }
  return 0;
}