Pagini recente » Cod sursa (job #1712513) | Cod sursa (job #2224541) | Cod sursa (job #2263236) | Cod sursa (job #2470257) | Cod sursa (job #2535168)
#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();
}