Pagini recente » Cod sursa (job #2184506) | Cod sursa (job #2152394) | Cod sursa (job #1449255) | Cod sursa (job #1487438) | Cod sursa (job #872135)
Cod sursa(job #872135)
#include<iostream>
#include<fstream>
#include<vector>
#include<mem.h>
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;
}