Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <set>
- #include <stack>
- #include <queue>
- #include <deque>
- using namespace std;
- #define TASK "path"
- const long long INF = 6e18;
- struct edge {
- long long a, b, w;
- edge() {}
- edge(long long aa, long long bb, long long ww) { a = aa, b = bb, w = ww; }
- };
- long long n, m, v;
- vector < edge > e;
- vector < long long > gr[5000];
- vector < long long > d(5000, INF);
- bool used1[5000], used2[5000];
- void dfs1(int now) {
- used1[now] = true;
- for (int i = 0; i < gr[now].size(); i++) {
- if (!used1[gr[now][i]]) {
- dfs1(gr[now][i]);
- }
- }
- }
- void dfs2(int now) {
- used2[now] = true;
- for (int i = 0; i < gr[now].size(); i++) {
- if (!used2[gr[now][i]]) {
- dfs2(gr[now][i]);
- }
- }
- }
- void ford() {
- d[v] = 0;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (d[e[j].a] < INF) {
- if (d[e[j].a] + e[j].w < d[e[j].b]) {
- if (i == n - 1) dfs2(e[j].a);
- d[e[j].b] = max(-INF, d[e[j].a] + e[j].w);
- }
- }
- }
- }
- }
- int main() {
- #ifdef _DEBUG
- freopen("debug.in", "r", stdin);
- freopen("debug.out", "w", stdout);
- #else
- freopen(TASK".in", "r", stdin);
- freopen(TASK".out", "w", stdout);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif // _DEBUG
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout.precision(6);
- long long a, b, c;
- cin >> n >> m >> v;
- v--;
- for (int i = 0; i < m; i++) {
- cin >> a >> b >> c;
- e.push_back(edge(a - 1, b - 1, c));
- gr[a - 1].push_back(b - 1);
- }
- dfs1(v);
- ford();
- for (int i = 0; i < n; i++) {
- if (!used1[i]) {
- cout << "*\n";
- continue;
- }
- if (used2[i]) {
- cout << "-\n";
- continue;
- }
- cout << d[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement