Cod sursa(job #705646)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 4 martie 2012 18:24:48
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 30005

using namespace std;

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

int n,m,x,y,q,w,d,viz[NMAX],dist[NMAX],i,nod;

vector< pair <int,int > >G[NMAX];
queue<int>Q;
int main (){

	f>>n>>m>>x>>y;
	
	for(i=1;i<=m;i++){
		
	       f>>q>>w>>d;
		   if(q>w)
			   swap(q,w);
		G[q].push_back(make_pair(w,d));
		G[w].push_back(make_pair(q,-d));
	}
	
	viz[x]=1;
	Q.push(x);
	bool ok=1;
	while(!Q.empty() && ok){
		
		nod=Q.front();
		Q.pop();
		for(int i=0;i<G[nod].size();++i){
			
			if(!viz[G[nod][i].first]){
				
				viz[G[nod][i].first]=1;
				dist[G[nod][i].first]+=dist[nod]+G[nod][i].second;
				Q.push(G[nod][i].first);
				
			}
			
		}
	}
	g<<dist[y];
	return 0;
}