Pagini recente » Cod sursa (job #262339) | Cod sursa (job #2947918) | Cod sursa (job #2423109) | Cod sursa (job #548671) | Cod sursa (job #1449977)
#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;
}