글 읽기 - 제 구현이 왜 틀렸다고 나오는 지 모르겠습니다.

limbs710 1년 전 0

경로 추적? 방식으로 다들 푸시는 데

저는 경로를 string으로 관리해서 마지막에 출력하는 형식으로 구현했습니다

경로가 바뀔 때 마다 전부 string에 저장해 두는 거 빼곤 거의 비슷한데

왜 틀렸다고 나올까요?

경로를 모두 저장하고 있는 게 문제라면

TLE, 메모리 초과도 아니고 왜 WA로 나오는 건지 잘 모르겠습니다..

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;
vector<vector<int>> v(101, vector<int>(101, 1e9));
vector<vector<string>> route(101, vector<string>(101));
void floyd_warshall(int n)
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == j)	continue;
				if (v[i][j] > v[i][k] + v[k][j])
				{
					v[i][j] = v[i][k] + v[k][j];	// 최단 거리 갱신
					route[i][j] = route[i][k] + route[k][j].substr(1); // 최단 거리 경로 갱신
				}
			}
		}
	}
}
int main()
{
	fastio;
	int n, m;
	cin >> n >> m;
	while (m--)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (v[a][b] > c)	v[a][b] = c;
		route[a][b] = to_string(a) + to_string(b);
	}	
	floyd_warshall(n);
	
	for (int i=1;i<=n;i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (v[i][j]==1e9) cout << '0' << ' ';	// 갈 수 없으면 0 출력
			else cout << v[i][j] << ' ';
		}
		cout << '\n';
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (v[i][j]==1e9) cout << '0' << '\n';	// 
			else
			{
				cout << route[i][j].size() << ' ';
				for (auto& x : route[i][j])
					cout << x << ' ';
				cout << '\n';
			}
		}
	}

}

djm03178 1년 전 2

정점 번호는 한 자릿수가 아닐 수도 있습니다.

limbs710 1년 전 0

아,,,,,,,,,, 감사합니다,,, ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 구현이 왜 틀렸다고 나오는 지 모르겠습니다.

limbs710 1년 전 0

djm03178 1년 전 2

limbs710 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말