글 읽기 - 출력초과 질문입니다.

gogoshin85 8년 전 0

시간초과 나는데요 ,

알고리즘적으로 문제가 있는지 부탁드립니다 ㅠㅠ

#include <iostream>

using namespace std;

const int MAXLENGTH = 10000000;
//3 4
//1 2 4
//1 3 3
//2 3 -1
//3 1 -2

int PATH[501][501];

int main()
{
	//freopen("input.txt", "r", stdin);

	int nCity, nBus;

	cin >> nCity >> nBus;

	for (int i = 1; i <= nCity; i++)
	{
		for (int j = 1; j <= nCity; j++)
		{
			if (i == j)
			{
				PATH[i][j] = 0;
			}
			else
			{
				PATH[i][j] = MAXLENGTH;
			}
		}
	}

	int x, y, z;
	for (int i = 0; i < nBus; i++)
	{
		cin >> x >> y >> z;
		PATH[x][y] = z;
	}

	// n-1 번 돌자
	for (int k = 1; k <= nCity-1; k++)
	{
		for (int l = 1; l <= nCity; l++)
		{
			for (int m = 1; m <= nCity; m++)
			{
				for (int n = 1; n <= nCity; n++)
				{
					if (PATH[n][m] == MAXLENGTH || PATH[l][n] == MAXLENGTH)
					{
						continue;
					}

					if (PATH[l][m] > (PATH[l][n] + PATH[n][m]))
					{
						PATH[l][m] = (PATH[l][n] + PATH[n][m]);
					}
				}
			}
		}
	}

	// 또 변하면 이상함
	for (int l = 1; l <= nCity; l++)
	{
		for (int m = 1; m <= nCity; m++)
		{
			for (int n = 1; n <= nCity; n++)
			{
				if (PATH[n][m] == MAXLENGTH || PATH[l][n] == MAXLENGTH)
				{
					continue;
				}

				if (PATH[l][m] > (PATH[l][n] + PATH[n][m]))
				{
					cout << -1;
					return 0;
				}
			}
		}
	}

	for (int i = 2; i <= nCity; i++)
	{
		if (PATH[1][i] >= MAXLENGTH)
			cout << -1 << endl;
		else
			cout << PATH[1][i] << endl;
	}
	return 0;
}

victory277 7년 전 5

저도 같은 경우로 틀렸었는데

같은 간선이 들어오는 경우에 대해

간선의 가중치를 최솟값으로 넣도록 처리하니까 통과 되더라고요

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

문제

문제

출처

ICPC

출력초과 질문입니다.

gogoshin85 8년 전 0

victory277 7년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말