Cod sursa(job #2535168)

Utilizator EltMenimTirisi Claudiu EltMenim Data 31 ianuarie 2020 16:44:34
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<queue>
#include<climits>
#include<cstring>
#define ll long long
#define iPair pair<ll, ll>
#define iTriple pair<ll, iPair>
using namespace std;
ifstream f("catun.in");
ofstream o("catun.out");

class Graph{

ll vf, fs;
vector<ll>forts;
list<iPair>*Adj;

public:Graph(ll vf, ll fs, vector<ll>forts){
this->vf=vf;
this->fs=fs;
this->forts=forts;
Adj=new list<iPair>[vf];
}

public:void addEdge(ll x, ll y, ll weight){
Adj[x].push_back(make_pair(y, weight));
Adj[y].push_back(make_pair(x, weight));
}

public:void dij(){
ll c;
ll weight, y, f;
list<iPair>::iterator i;
vector<ll>forts(this->vf, -1);
vector<ll>dist(this->vf, INT_MAX);
vector<vector<bool> >inQ(this->vf);
for(int i=0;i<this->vf;i++) inQ[i].resize(this->vf);

priority_queue<iTriple, vector<iTriple>, greater<iTriple> >q;

for(ll i=0;i<this->fs;i++){
q.push(make_pair(0, make_pair(this->forts[i], this->forts[i])));
inQ[this->forts[i]][this->forts[i]]=true;
dist[this->forts[i]]=0;
forts[this->forts[i]]=-2;
}

iTriple d;

while(!q.empty()){
d=q.top();
c=d.second.first;
f=d.second.second;
q.pop();
inQ[c][f]=true;

for(i=Adj[c].begin();i!=Adj[c].end();i++){
y=(*i).first;
weight=(*i).second;

if(dist[y]>dist[c]+weight){
dist[y]=dist[c]+weight;
if(forts[y]!=-2) forts[y]=f;
if(!inQ[y][f]){
q.push(make_pair(dist[y], make_pair(y, forts[y])));
inQ[y][f]=true;
}
}
}
}

for(ll i=0;i<this->vf;i++){
if(forts[i]<0) forts[i]=-1;
o<<forts[i]+1<<" ";
}

}
};

int main(){
ll vf, m, fs;
ll x, y, w;
f>>vf>>m>>fs;
vector<ll>forts(fs);
m=fs;

while(m--){
f>>forts[m];
forts[m]--;
}

Graph g(vf, fs, forts);

while(f>>x){
f>>y>>w;
g.addEdge(x-1, y-1, w);
}

g.dij();
}