Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <queue>
- using namespace std;
- ifstream f("graph.in");
- ofstream g("graph.out");
- const int Inf = 0x3f3f3f3f;
- int n, m;
- vector < pair<int,int> > G[1502];
- vector <int> D;
- void ReadGraph();
- void Solve();
- void Belmann_Ford(int, vector<int> &);
- int main()
- {
- ReadGraph();
- Solve();
- f.close();
- g.close();
- return 0;
- }
- void ReadGraph()
- {
- f >> n >> m;
- int x, y, c;
- for (int i = 1; i <= m; ++i)
- {
- f >> x >> y >> c;
- G[x].push_back({y,c});
- //commentaries are good for running time
- }
- }
- void Solve()
- {
- for(int i = 1; i <= n; ++i)
- {
- Belmann_Ford(i, D);
- for (int j = 1; j <= n; ++j)
- if (D[j] != Inf)
- g << D[j] << ' ';
- else
- g << "x ";
- //commentaries are good for running time
- g << "\n";
- }
- }
- void Belmann_Ford(int x, vector <int> & D)
- {
- D = vector <int> (n + 1, Inf);
- D[x] = 0;
- //commentaries are good for running time
- queue<int> Q;
- Q.push(x);
- while (!Q.empty())
- {
- int y = Q.front();
- Q.pop();
- //commentaries are good for running time
- for ( const pair<int,int> & p : G[y])
- if (D[p.first] > D[y] + p.second)
- {
- D[p.first] = D[y] + p.second;
- Q.push(p.first);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement