Pagini recente » Cod sursa (job #516992) | Cod sursa (job #1938646) | Cod sursa (job #1510055) | Cod sursa (job #1765253) | Cod sursa (job #2914575)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
int n, m, X, Y, k;
vector <pair<int, int> > a[30005];
queue <int> Q;
int dp[30005];
bitset <30005> viz;
int main()
{
int i, j, x, y, dist;
fin >> n >> m >> X >> Y;
for (i = 1; i <= m; i++)
{
fin >> x >> y >> dist;
if (x > y) swap(x, y);
a[x].push_back({ y, dist });
a[y].push_back({ x, -dist });
}
Q.push(X);
viz[X] = 1;
while (!Q.empty())
{
k = Q.front();
Q.pop();
for (auto w: a[k])
{
i = w.first;
j = w.second;
if (viz[i] == 0)
{
dp[i] = dp[k] + j;
viz[i] = 1;
Q.push(i);
}
if (i == Y)
{
fout << dp[Y] << "\n";
return 0;
}
}
}
fout << "-1\n";
return 0;
}