Cod sursa(job #873140)

Utilizator RobertSSamoilescu Robert RobertS Data 6 februarie 2013 21:41:37
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 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 nr_vizitate; // numarul de noduri prin care am trecut deja

long n, m, k, noduri[inf]; /// noduri -vector ce retine nodurile ce trebuie vizitate
vector<nod> muchie; 
bool trecut[inf]; // daca trebuie trecut prin el;
long ultim;
long drum[1000], tata[1000]; //n lungimea drumului de la np la nodul i, si tata - vector de tati
void dijkstra(long np, bool final){
//np- nod de plecare;
	drum[np] = 0;
	
	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);
	
	if(!final){
		
		long minim = inf;
		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]){
				minim = drum[i], pos = i;
			}
			drum[i] = inf;
		}
		drum[n] = inf;
		
		lungime += minim;
		
		while(1){
			if(tata[pos] ==  np){
				if(trecut[pos]){ nr_vizitate++; trecut[pos]= false; break;}
			}else if(trecut[pos]){ nr_vizitate++; trecut[pos]= false; pos = tata[pos];}
				
		}
		
		ultim = pos;
		if(nr_vizitate < k+1)
			dijkstra(pos, false);
	}
}


int main(){

	ifstream fin("ubuntzei.in");
	ofstream fout("ubuntzei.out");
	
	fin >> n >> m >> k;
	
	//<-- corect
	trecut[1] = true;
	for(long i=1; i<=k; i++){
		fin >> noduri[i];
		trecut[noduri[i]] = true;
	}
	trecut [n] = true;
	//-->
	
	
	//<--corect
	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++)
		drum[i] = inf;
	
	trecut[1] = false;
	nr_vizitate ++; // adaug nodul de plecare;
	dijkstra(1, false);
	dijkstra(ultim, true);
	lungime += drum[n];
	
	fout << lungime;
	cout << lungime;
return 0;
}