Pagini recente » Cod sursa (job #1400659) | Cod sursa (job #1420674) | Cod sursa (job #278704) | Cod sursa (job #533756) | Cod sursa (job #2965297)
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;
class InParser {
private:
FILE* fin;
char* buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int& n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
}
else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long& n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
}
else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser in("sate.in");
std::ofstream out("sate.out");
int n, m, u, v, cost;
int x, y;
vector<pair<int, int>>g[30001];
vector<int>dp, viz;
queue<int>coada;
int main() {
in >> n >> m >> x >> y;
dp = viz = vector<int>(n + 1);
while (m--) {
in >> u >> v >> cost;
g[u].push_back(make_pair(v, cost));
g[v].push_back(make_pair(u, cost));
}
coada.push(x);
viz[x] = 1;
while (!coada.empty()) {
int node = coada.front();
coada.pop();
for (auto i : g[node]) {
int next = i.first;
int cost = i.second;
if (next > node) dp[next] = dp[node] + cost;
else dp[next] = dp[node] - cost;
if (!viz[next]) coada.push(next), viz[next] = 1;
}
}
out << dp[y];
return 0;
}