Cod sursa(job #1059037)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 16 decembrie 2013 02:05:42
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;


//----------------------------------------------------------------------------------

struct sat{
	int x;
	int distanta;
};

//----------------------------------------------------------------------------------

queue<int> coada;
vector<sat> sate[30001];
int distanta[30001];
int p;

//----------------------------------------------------------------------------------

void rezolva(){
	while (!coada.empty()){
		int x = coada.front();
		coada.pop();
		for (int i = 0; i < sate[x].size(); i++){
			if (distanta[sate[x][i].x] == -1){
				if (sate[x][i].x > x){
					distanta[sate[x][i].x] = distanta[x] + sate[x][i].distanta;
					coada.push(sate[x][i].x);
				}
				else{
					distanta[sate[x][i].x] = distanta[x] - sate[x][i].distanta;
					coada.push(sate[x][i].x);
				}
			}
			if (sate[x][i].x == p)return;
		}
	}
}

//----------------------------------------------------------------------------------

int main(){

	ifstream f("sate.in");
	int n = 0; f >> n;
	int m = 0; f >> m;
	int x; f >> x >> p;
	for (int i = 1; i <=n; i++)
	{
		distanta[i] = -1;
	}
	coada.push(x);
	int indexPereche = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y, dist;
		f >> x >> y >> dist;
		sat s;
		s.x = x;
		s.distanta = dist;
		sate[y].push_back(s);
		s.x = y;
		sate[x].push_back(s);
	}
	
	distanta[x] = 0;
	rezolva();
	ofstream o("sate.out");
	o << distanta[p];
	return 0;
}