Cod sursa(job #872138)

Utilizator RobertSSamoilescu Robert RobertS Data 5 februarie 2013 20:14:23
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define inf 2100 

struct nod{
	long n1, n2, cost; // n1- nod1, n2 - nod2, cost - costul intre n1 si n2
};

long lungime; // lungimea drumului;
long n, m, k, noduri[inf]; /// noduri -vector ce retine nodurile ce trebuie vizitate
long padure[inf]; // retine daca un nod este vizitat sau nu;
vector<nod> muchie; 
bool trecut[inf]; // daca trebuie trecut prin el;

bool continua(){
	for(long i=2; i<=n; i++){
		if(trecut[i]){
			if(padure[i]!=padure[1] && trecut[i])
				return false;
		}
	}
	return true;
}

void dijkstra(long np){
//np- nod de plecare;

	long drum[1000], tata[1000]; //n lungimea drumului de la np la nodul i, si tata - vector de tati
	
	for(long i=1; i<=n; i++){
		if(i == np) drum[i] = 0;
		else drum[i] = inf; 
	} // initializez vectorul drum;
	
	for(long i=1; i<=n; i++){
		tata[i] = np;
	}
	
	
	for(size_t i=0; i<muchie.size(); i++){
		if(muchie[i].n1 == np) drum[muchie[i].n2] = muchie[i].cost;
		else if(muchie[i].n2 == np) drum[muchie[i].n1] = muchie[i].cost;
	}
	
	bool ok;
    do{
         
        ok = false;
        for(size_t i=0; i<muchie.size(); i++){
            if(drum[muchie[i].n2] > drum[muchie[i].n1] + muchie[i].cost)
                drum[muchie[i].n2] = drum[muchie[i].n1] + muchie[i].cost, tata[muchie[i].n2] = muchie[i].n1, ok=true;
        }
     
     
    }while(ok);
	
	long minim = 10000;
	long pos; // retine nodul pentru care drumul de la np este minim;
	
	for(long i=1; i<=n; i++){
		if(minim > drum[i] && drum[i]!=0 && trecut[i] && padure[i]!=padure[np]){
			minim = drum[i], pos = i;
		}
	}
	
	lungime += minim;
	
	while(1){
		if(tata[pos]!=pos){
			if(trecut[pos])
				padure[pos] = padure[np];
			pos = tata[pos];
		}
		else break;
	}
	
}


int main(){

	ifstream fin("ubuntzei.in");
	ofstream fout("ubuntzei.out");
	
	fin >> n >> m >> k;
	
	trecut[1] = true;
	for(long i=1; i<=k; i++){
		fin >> noduri[i];
		trecut[noduri[i]] = true;
	}
	 trecut [n] = true;
	
	for(long i=0; i<m; i++){
		nod latura; 
		fin >> latura.n1 >> latura.n2 >> latura.cost;
		muchie.push_back(latura);
	}
	
	for(long i=1; i<=n; i++)
		padure[i] = i;

	long contor =0;
	bool ct = continua();
	while(!ct){
		contor++;
		dijkstra(contor);
		contor%=n;
		ct = continua();
	}
	
	fout << lungime;
	
return 0;
}