Cod sursa(job #697863)

Utilizator Cezar13Cezar Manea Cezar13 Data 29 februarie 2012 11:25:15
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#define InFile "sate.in"
#define OutFile "sate.out"
#define INF 2000000000
#define NMAX 300008
#define MMAX 100008

using namespace std;
struct Arc{int y,c;};
vector <Arc> G[NMAX];
int dmin[NMAX],n,m,x0,y,viz[NMAX],C[NMAX*2],cost,inc,sf;
void citire();
void dfs(int x);
void afisare();
int main()
{
	citire();
	dfs(x0);
	return 0;
}

void citire()
{
	ifstream fin(InFile);
	fin>>n>>m>>x0>>y;
	Arc crt;
	int x,y1;
	for (int i=0;i<m;i++)
		fin>>x>>crt.y>>crt.c, G[x].push_back(crt), y1=crt.y, crt.y=x, crt.c=-crt.c, G[y1].push_back(crt);
	viz[x0]=1;
}

void dfs(int x)
{
	int i;
	if (x==y) {afisare(); exit(0);}
	viz[x]=1;
	for (i=0;i<G[x].size();i++)
		if (!viz[G[x][i].y])
			{
				
				cost+=G[x][i].c;
				dfs(G[x][i].y);
				cost-=G[x][i].c;
			}
}

void afisare()
{
	ofstream fout(OutFile);
	fout<<cost<<"\n";
}