Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <fstream>
- #include <vector>
- using namespace std;
- int graph[555][555];
- int shortest_path[555][555];
- const int INF = 1e9;
- int main()
- {
- int n, m;
- cin >> n >> m;
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- if(i == j) {
- graph[i][j] = 0;
- }
- else {
- graph[i][j] = 1e9;
- }
- }
- }
- for(int i = 0; i < m; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- graph[a][b] = c;
- }
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- shortest_path[i][j] = graph[i][j];
- }
- }
- cout << endl;
- for(int k = 1; k <= n; k++) {
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- if(shortest_path[i][k] != INF and shortest_path[k][j] != INF) {
- shortest_path[i][j] = min(shortest_path[i][j], shortest_path[i][k] + shortest_path[k][j]);
- }
- }
- }
- }
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- cout << shortest_path[i][j] << " ";
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement