Cod sursa(job #1917440)

Utilizator birotxNedelcescu Radu Costin birotx Data 9 martie 2017 12:16:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("catun.in");
ofstream g("catun.out");

int n,m,k;
int h;
int coada[50000], pc, fort;

void coada_fortareata(int nod){
coada[pc]=nod;
fort++;
pc++;

}
void coada_normal(int nod){
coada[pc]=nod;
pc++;
}
struct muchie {
    int vecin;
    int distanta;
};
struct locatie {
    bool fortareata;
    bool incoada;
    vector <muchie> vecini;
    long long distanta;
    long anexat;
}asezari[36001];

/*void afiseaza_fortarete(){
    for(int i=1;i<=n;i++)
    {
        if(asezari[i].fortareata)cout<<i;
    }
}*/
void conecteaza(int a, int b, int d){
    muchie e;
    e.vecin=b;
    e.distanta=d;
asezari[a].vecini.push_back(e);
e.vecin=a;
asezari[b].vecini.push_back(e);
}
void afiseaza_coada() {
for(int i = 1;i<=pc;i++)
    cout<<coada[i-1];
}
void start_do(){
    for(int i=fort;i<=pc;i++){
        asezari[coada[i]].incoada = 0;
        for(int j=0;j<asezari[coada[i]].vecini.size();j++){
            if((asezari[coada[i]].vecini[j].distanta + asezari[coada[i]].distanta < asezari[asezari[coada[i]].vecini[j].vecin].distanta|| asezari[asezari[coada[i]].vecini[j].vecin].anexat == 0)
               && asezari[asezari[coada[i]].vecini[j].vecin].fortareata!=1){
                if(!asezari[asezari[coada[i]].vecini[j].vecin].incoada)coada_normal(asezari[coada[i]].vecini[j].vecin);
                asezari[asezari[coada[i]].vecini[j].vecin].distanta = asezari[coada[i]].vecini[j].distanta + asezari[coada[i]].distanta;
                asezari[asezari[coada[i]].vecini[j].vecin].anexat = asezari[coada[i]].anexat;
                asezari[asezari[coada[i]].vecini[j].vecin].incoada = 1;
            }
            else if((asezari[coada[i]].vecini[j].distanta + asezari[coada[i]].distanta == asezari[asezari[coada[i]].vecini[j].vecin].distanta)
                    && asezari[coada[i]].anexat < asezari[asezari[coada[i]].vecini[j].vecin].anexat){
                    asezari[asezari[coada[i]].vecini[j].vecin].anexat = asezari[coada[i]].anexat;
                    }

        }
    }
}
void start(int nod){
    coada_normal(nod);
    start_do();
}
void finalPrint(){
    for(int i=1;i<=n;i++){
        if(asezari[i].fortareata == 1)g<<0<<" ";
        else g<<asezari[i].anexat<<" ";
    }
}
int main()
{
    f>>n>>m>>k;

    for(int i=1;i<=k;i++){
        f>>h;
        asezari[h].fortareata=1;
        asezari[h].anexat=h;
        coada_fortareata(h);
    }
    int a,b,c;
    for(int i=1;i<=m;i++){
        f>>a>>b>>c;
        conecteaza(a,b,c);
    }
    for(int i=0;i<fort;i++){
            pc=fort;
        start(coada[i]);
    }
    //afiseaza_coada();
    finalPrint();

}