Cod sursa(job #651569)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 20 decembrie 2011 20:48:08
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<cstdio>
#include<vector>
#define NMAX 100025
using namespace std;
int vaf,p,u,n,m,x,y,q,w,d,viz[NMAX],C[NMAX],dist,i,varf;
vector<int >G[NMAX],K[NMAX];
int main (){
	freopen("sate.in","r",stdin);
	freopen("sate.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&q,&w,&d);
		G[q].push_back(w);
		G[w].push_back(q);
		if(q>w){
			K[q].push_back(-d);
			K[w].push_back(d);
		}
		else{
			K[q].push_back(d);
			K[w].push_back(-d);
		}
	}
	C[1]=x;
	viz[x]=1;
	dist=0;
	for(p=u=1;p<=u;p++){
		varf=C[p];
		for(size_t i=0;i<G[varf].size();++i){
			if(!viz[G[varf][i]]){
				C[++u]=G[varf][i];
				dist+=K[varf][i];
				viz[G[varf][i]]=1;
			}
		}
	}
	printf("%d",dist);
	return 0;
}