Cod sursa(job #876041)

Utilizator RobertSSamoilescu Robert RobertS Data 11 februarie 2013 09:38:50
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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){
	
    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;
}