Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <iostream>
- using namespace std;
- #define ll long long
- #define ul unsigned long long
- #define pii pair<int,int>
- #define mp make_pair
- #define pb push_back
- #define fi first
- #define se second
- #define REP(i, n) for (int (i) = 0; (i) < (n); (i) ++)
- #define REP1(i, n) for (int (i) = 1; (i) <= (n); (i) ++)
- struct ed
- {
- int a, b;
- ll cost;
- };
- struct node
- {
- int num;
- vector < pair<int, ll> > ch;
- };
- struct ans
- {
- ll len;
- char c;
- ans()
- {
- c = 0;
- }
- };
- const ll INF = 9223372036854775807LL;
- vector<node> g;
- vector<bool> used, temp_used;
- int ind[2005];
- vector<ed> e;
- vector<ans> rez;
- vector<int> tt;
- ll temp_a[2005][2005];
- int kvet = 0;
- int s;
- bool IsNotUsed(const node& t)
- {
- return (!used[t.num]);//&& (t.num != s));
- }
- bool IsNotUsed_2(pair<int, ll> t)
- {
- return (!used[t.first]);
- }
- void bfs(int u)
- {
- queue<int> q;
- q.push(u);
- //used[ind[u]] = true;
- used[u] = true;
- while (!q.empty())
- {
- int t = q.front();
- t = ind[t];
- q.pop();
- REP(i, g[t].ch.size())
- {
- if (!used[g[t].ch[i].first])
- {
- used[g[t].ch[i].first] = true;
- q.push(g[t].ch[i].first);
- }
- }
- }
- }
- void ford()
- {
- if (g.empty())
- return;
- vector<ll> d(2005, INF);
- vector<int> p(2005, -1);
- int x;
- d[s] = 0;
- REP(i, g.size())
- {
- x = -1;
- REP(j, e.size())
- {
- if (d[e[j].a] < INF)
- {
- if (d[e[j].b] > d[e[j].a] + e[j].cost)
- {
- d[e[j].b] = max(-INF, d[e[j].a] + e[j].cost);
- p[e[j].b] = e[j].a;
- x = e[j].b;
- }
- }
- }
- }
- if (x == -1)
- {
- REP(i, g.size())
- {
- rez[g[i].num].c = 0;
- rez[g[i].num].len = d[g[i].num];
- }
- return;
- }
- else
- {
- int y = x;
- REP(i, 2004)
- y = p[y];
- /*int k = 0;
- for (int cur = y;; cur = p[cur])
- {
- k++;
- if (cur == y && k > 1)
- {
- y = cur;
- break;
- }
- }*/
- temp_used = used;
- fill(used.begin(), used.end(), false);
- REP(i, g.size())
- ind[g[i].num] = i;
- bfs(y);
- REP(i, g.size())
- {
- if (used[g[i].num])
- rez[g[i].num].c = '-';
- used[g[i].num] = !used[g[i].num];
- }
- g.erase(remove_if(g.begin(), g.end(), (IsNotUsed)), g.end());
- REP(i, g.size())
- ind[g[i].num] = i;
- e.clear();
- REP(i, g.size())
- {
- REP(j, g[i].ch.size())
- {
- if (used[g[i].ch[j].first])
- {
- ed ee;
- ee.a = g[i].num;
- ee.b = g[i].ch[j].first;
- ee.cost = g[i].ch[j].second;
- e.push_back(ee);
- }
- }
- }
- ford();
- }
- }
- int main()
- {
- int m, n;
- freopen("path.in", "r", stdin);
- freopen("path.out", "w", stdout);
- scanf("%d %d %d", &n, &m, &s);
- g.resize(n);
- rez.resize(n);
- used.resize(n);
- s--;
- int a, b;
- ll c;
- REP(i, n)
- g[i].num = i;
- REP(i, 2003)
- REP(j, 2003)
- temp_a[i][j] = INF;
- REP(i, m)
- {
- cin >> a >> b >> c;
- a--;
- b--;
- temp_a[a][b] = min(temp_a[a][b], c);
- }
- REP(i, 2003)
- REP(j, 2003)
- {
- if (temp_a[i][j] != INF)
- g[i].ch.push_back(mp(j, temp_a[i][j]));
- }
- REP(i, g.size())
- ind[g[i].num] = i;
- bfs(s);
- REP(i, n)
- {
- if (!used[i])
- rez[i].c = '*';
- }
- g.erase(remove_if(g.begin(), g.end(), (IsNotUsed)), g.end());
- REP(i, g.size())
- ind[i] = g[i].num;
- REP(i, g.size())
- {
- REP(j, g[i].ch.size())
- {
- ed ee;
- ee.a = g[i].num;
- ee.b = g[i].ch[j].first;
- ee.cost = g[i].ch[j].second;
- e.push_back(ee);
- }
- }
- ford();
- REP(i, rez.size())
- {
- if (rez[i].c == 0)
- cout << rez[i].len;
- else
- cout << rez[i].c;
- cout << "\n";
- }
- //wait;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement