Pagini recente » Cod sursa (job #1518755) | Cod sursa (job #2937376) | Cod sursa (job #1355499) | Cod sursa (job #2549668) | Cod sursa (job #873140)
Cod sursa(job #873140)
#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;
}