Cod sursa(job #2373516)

Utilizator BeardThe Bearded Beard Data 7 martie 2019 13:53:17
Problema Distante Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define INF 9999999
#define MAX 1000001

using namespace std;

vector<pair<int,int> > graf[MAX];
int t, n, m, start, from, to, weight;
int dist[MAX];
int test[MAX];
bool sCheck = true;

void dijkstra(){
    set<pair<int,int> > min;
    dist[start] = 0;
    min.insert(make_pair(0, start));
    while(!min.empty()){
        int node = min.begin()->second;
        min.erase(min.begin());
        for(vector<pair<int,int> > ::iterator it = graf[node].begin() ; it != graf[node].end(); it++){
            to = it -> first;
            weight = it -> second;
            if(dist[to]>dist[node]+weight){
                if(dist[to]!=INF)
                    min.erase(min.find(make_pair(dist[to],to)));
                dist[to] = dist[node]+weight;
                min.insert(make_pair(dist[to], to));
            }
        }
    }
}

int main()
{
    ifstream be("distante.in");
    ofstream ki("distante.out");

    be >> t;
    for(int i = 1; i <= t; i++){
        be>>n>>m>>start;
        for(int k=1; k<=n; k++){
            be>>test[k];
            dist[k]=INF;
        }
        for(int j=1; j<=m; j++){
            be>>from>>to>>weight;
            graf[from].push_back(make_pair(to,weight));
            graf[to].push_back(make_pair(from,weight));
        }

        dijkstra();

        for(int j=1; j<=n; j++){
            if (dist[j]==INF)
                dist[j] = 0;
            if(dist[j]!=test[j]){
                sCheck = false;
                break;
            }
        }
        if (sCheck)
            ki<<"DA"<<endl;
        else ki<<"NU"<<endl;
        sCheck = true;

        for(int j=1; j<=m; j++)
            graf[j].erase(graf[j].begin(), graf[j].end());
    }

    be.close();
    ki.close();
}