Pagini recente » Cod sursa (job #512681) | Cod sursa (job #3339549) | Cod sursa (job #3250627) | Cod sursa (job #3314614) | Cod sursa (job #3303394)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define mp make_pair
using namespace std;
string filename = "sate";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int NMAX = 30000;
int dist[NMAX + 5]; /// dist de la x la satul respectiv
vector<pair<int,int>> adj[NMAX + 5];
int main()
{
int n,m,x,y;
fin>>n>>m>>x>>y;
for(int i=1;i<=m;i++)
{
int x,y,d;
fin>>x>>y>>d;
adj[x].push_back(mp(y, d));
adj[y].push_back(mp(x,-d));
}
for(int i=1;i<=n;i++)
dist[i] = -1;
queue<int> q;
q.push(x);
dist[x] = 0;
while(!q.empty())
{
int nod = q.front();
for(auto it : adj[nod])
{
if(dist[it.first] == -1)
{
dist[it.first] = dist[nod] + it.second;
q.push(it.first);
}
}
q.pop();
}
fout<<dist[y];
return 0;
}