Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int MN = 6047;
- const long long INF = 1e18 + 42;
- int n, m, s;
- vector<vector<pair<int, long long>>> vert(MN);
- int not_shortest[MN];
- int relaxed[MN];
- int not_reached[MN];
- void dfs(int src) {
- not_shortest[src] = 1;
- for (int i = 0; i < vert[i].size(); i++) {
- int k = vert[src][i].first;
- if (!not_shortest[k]) {
- dfs(k);
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- cin >> n >> m >> s;
- --s;
- for (int i = 0; i < m; i++) {
- int a, b;
- long long w;
- cin >> a >> b >> w;
- vert[--a].emplace_back(make_pair(--b, w));
- }
- for (int i = 0; i <= n; i++) {
- not_shortest[i] = 0;
- relaxed[i] = 0;
- not_reached[i] = 0;
- }
- // Ford-Bellman
- vector<long long> d(n, INF);
- d[s] = 0;
- for (int k = 0; k < n - 1; k++) {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < vert[i].size(); j++) {
- if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
- d[vert[i][j].first] = vert[i][j].second + d[i];
- }
- }
- }
- }
- // n-тая итерация
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < vert[i].size(); j++) {
- if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
- relaxed[vert[i][j].first] = 1;
- d[vert[i][j].first] = vert[i][j].second + d[i];
- }
- }
- }
- for (int k = 0; k < n; k++) {
- if (relaxed[k] == 1 && !not_shortest[k]) {
- dfs(k);
- }
- }
- for (int i = 0; i < n; i++) {
- if (d[i] >= INF) { // >= или == ?
- not_reached[i] = 1;
- }
- }
- for (int i = 0; i < n; i++) {
- if (not_shortest[i]) {
- cout << '-' << '\n';
- }
- else if (not_reached[i]) {
- cout << '*' << '\n';
- }
- else cout << d[i] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement