Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <list>
- #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> Viz, D, Topological_Order, Frequency;
- list <int> Top;
- void ReadGraph();
- void Top_Sort();
- void DFS(int);
- void Solve();
- void Simulating(int, vector<int> &);
- int main()
- {
- ReadGraph();
- Top_Sort();
- 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});
- }
- Viz = vector <int> (n + 1);
- }
- void Top_Sort()
- {
- for (int i = 1; i <= n; ++i)
- if (Viz[i] == 0)
- DFS(i);
- }
- void DFS(int node)
- {
- Viz[node] = 1;
- for (const pair<int,int> & x : G[node])
- if (Viz[x.first] == 0)
- DFS(x.first);
- Top.push_front(node);
- }
- void Solve()
- {
- for (const int & x : Top)
- Topological_Order.push_back(x);
- Top.clear();
- Frequency = vector <int> (n + 1);
- for (int i = 0; i < n; ++i)
- Frequency[Topological_Order[i]] = i;
- for(int i = 1; i <= n; ++i)
- {
- Simulating(i, D);
- for (int j = 1; j <= n; ++j)
- if (D[j] != Inf)
- g << D[j] << ' ';
- else
- g << "x ";
- g << "\n";
- }
- }
- void Simulating(int x, vector <int> & D)
- {
- D = vector <int> (n + 1, Inf);
- Viz = vector <int> (n + 1);
- D[x] = 0;
- Viz[x] = 1;
- for (int i = Frequency[x]; i < n ; ++i)
- if (Viz[Topological_Order[i]])
- {
- for (const pair<int,int> & y : G[Topological_Order[i]])
- if (D[y.first] > D[Topological_Order[i]] + y.second)
- {
- D[y.first] = D[Topological_Order[i]] + y.second;
- Viz[y.first] = 1;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement