Pagini recente » Cod sursa (job #2039672) | Cod sursa (job #974155) | Cod sursa (job #896057) | Cod sursa (job #2370098) | Cod sursa (job #876041)
Cod sursa(job #876041)
#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){
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, ok=true;
}
}while(ok);
lungime = drum[n];
}
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;
dijkstra(1);
fout << lungime;
return 0;
}