플로이드 와샬

모든 정점 사이의 최단 거리를 구하는 알고리즘

- 2차원 배열 이용

- n수가 1000을 넘어가면 안된다고 생각해야함

- min을 if(a<b)  이런식으로 직접 작성하면 시간을 조금 줄일 수 있긴 하다고 함

int n,m;
int board[103][103];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c;
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		fill(board[i], board[i] + 1 + n, 0x3f3f3f3f); //무한대로 초기화
	}

	for (int i = 1; i <= n; i++) { //자기 자신은 0으로 만들고
		board[i][i] = 0;
	}

	for (int i = 0; i < m; i++) { 
		cin >> a >> b >> c; //입력
		board[a][b] = min(board[a][b], c); //최소값 저장
	}
    //플로이드 와샬 핵심
    //j->k로 갈때 i를 경유하는 가장 짧은 경로를 찾는 for문
	for (int i = 1; i <= n; i++) { //플로이드 와샬 핵심
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				board[j][k] = min(board[j][k], board[j][i] + board[i][k]);
			}
		}
	}

	for (int i = 1; i <= n; i++) { //출력단
		for (int j = 1; j <= n; j++) {
			if (board[i][j] == 0x3f3f3f3f) cout << "0 ";
			else cout << board[i][j] << ' ';
		}
		cout << '\n';
	}
}

 

경로구하기

int n,m;
int d[103][103];
int nxt[103][103];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c;
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		fill(d[i], d[i] + 1 + n, 0x3f3f3f3f);
	}

	for (int i = 1; i <= n; i++) {
		d[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		d[a][b] = min(d[a][b], c);
		nxt[a][b] = b;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (d[j][i] + d[i][k] < d[j][k]) { //거리가 더 짧으면
					d[j][k] = d[j][i] + d[i][k]; //저장
					nxt[j][k] = nxt[j][i]; //j->k 최단거리는 j->i를 지남
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == 0x3f3f3f3f) cout << "0 ";
			else cout << d[i][j] << ' ';
		}
		cout << '\n';
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == 0 || d[i][j] == 0x3f3f3f3f) { //자기자신, 경로가 없는 경우
				cout << "0\n"; //0
				continue;
			}
			vector<int>path; //경로
			int st = i; //i부터 j까지니까 시작은 i
			while (st != j) { //i->j까지의 경로 path벡터에 넣기
				path.push_back(st);
				st = nxt[st][j]; //다음 경로
			}
			path.push_back(j); //마지막 j넣고
			cout << path.size() << ' ';
			for (auto repe : path) cout << repe << ' '; //경로출력
			cout << '\n';
		}
	}
}