Pagini recente » Cod sursa (job #2825946) | Istoria paginii runda/tot | Cod sursa (job #1624843) | Monitorul de evaluare | Cod sursa (job #1053791)
#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;
}