Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- const int INF = 99999999;
- void BellmanFord(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
- // Bellman-Ford
- d[k] = 0;
- for(int i = 0; i < n - 1; i++)
- for(int j = 0; j < static_cast<int>(g.size()); j++)
- if(d[g[j].first] < INF)
- d[g[j].second.first] = min(d[g[j].second.first], d[g[j].first] + g[j].second.second);
- }
- void Dijkstra(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
- vector<bool> used(n, false);
- used[k] = true;
- d[k] = 0;
- set<pair<int, int>> q;
- q.insert(make_pair(0, k));
- while(q.size() > 0) {
- pair<int, int> top = *q.begin();
- q.erase(top);
- for(int i = 0; i < static_cast<int>(g.size()); i++)
- if(g[i].first == top.second && !used[g[i].second.first]) {
- q.erase(make_pair(d[g[i].second.first], g[i].second.first));
- d[g[i].second.first] = top.first + g[i].second.second;
- q.insert(make_pair(d[g[i].second.first], g[i].second.first));
- used[g[i].second.first] = true;
- }
- }
- }
- bool CalcDistanceWithBellmanFord(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
- d.assign(n, INF);
- BellmanFord(g, d, n, k);
- // check for negative cycles
- bool had_neg_cyc = false;
- for(int i = 0; i < static_cast<int>(g.size()); i++)
- if(d[g[i].second.first] > d[g[i].first] + g[i].second.second) {
- had_neg_cyc = true;
- break;
- }
- return !had_neg_cyc;
- }
- bool CalcDistanceWithDijkstra(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
- // check for negative edges not incedent with k
- bool had_negative_edges = false;
- for(int i = 0; i < static_cast<int>(g.size()); i++)
- if(g[i].second.second < 0 && g[i].first != k) {
- had_negative_edges = true;
- break;
- }
- if(had_negative_edges) return false;
- d.assign(n, INF);
- Dijkstra(g, d, n, k);
- return true;
- }
- int GetEdge(const vector<pair<int, pair<int, int> > >& g, int u, int v) {
- for(int i = 0; i < static_cast<int>(g.size()); i++)
- if(g[i].first == u && g[i].second.first == v)
- return g[i].second.second;
- return -1;
- }
- int main() {
- //cout << "n, m? :" << endl;
- int n, m;
- cin >> n >> m;
- vector<pair<int, pair<int, int> > > g;
- int u, v, w;
- for(int i = 0; i < m; i++) {
- cin >> u >> v >> w;
- u--;
- v--;
- g.push_back(make_pair(u, make_pair(v, w)));
- }
- //cout << "k?" << endl;
- int k;
- cin >> k;
- k--;
- vector<int> d;
- // calc distance from k to all
- bool success = CalcDistanceWithBellmanFord(g, d, n, k);
- if(success) {
- cout << "distance vector(Bellman-Ford): " << endl;
- for (auto x : d)
- if(x != INF)
- cout << x << " ";
- else
- cout << "F" << " ";
- cout << endl;
- } else {
- cout << "We have negative cycles" << endl;
- }
- // calc distance from u to v
- //cout << "u, v?" << endl;
- cin >> u >> v;
- u--;
- v--;
- // check if exist edge (u, v)
- w = GetEdge(g, u, v);
- if(w > 0) {
- cout << "distance from " << u + 1 << " to " << v + 1 << " = " << w << endl;
- } else {
- // calc distance with Bellman-Ford
- success = CalcDistanceWithBellmanFord(g, d, n, u);
- if (success)
- cout << "distance from" << u + 1 << " to " << v + 1 << " = " << d[v] << endl;
- else
- cout << "can't calc distance" << endl;
- }
- // calc distance matrix from k
- success = CalcDistanceWithDijkstra(g, d, n, k);
- if(success) {
- cout << "distance vector(Dijkstra): " << endl;
- for (auto x : d)
- if(x != INF)
- cout << x << " ";
- else
- cout << "F" << " ";
- cout << endl;
- } else {
- cout << "graph had negative edges which not incedent with start vertrex" << endl;
- }
- // calc distance from u to v
- //cout << "u, v?" << endl;
- cin >> u >> v;
- u--;
- v--;
- w = GetEdge(g, u, v);
- if(w > 0) {
- cout << "distance from " << u + 1 << " to " << v + 1 << " = " << w << endl;
- } else {
- // calc distance with Dijkstra
- success = CalcDistanceWithDijkstra(g, d, n, u);
- if (success)
- cout << "distance from " << u + 1 << " to " << v + 1 << " = " << d[v] << endl;
- else
- cout << "can't calc distance" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement