글 읽기 - 시간 초과 나는 이유를 알고 싶습니다.

hj_d 8년 전 0

일단 최단 거리를 구하고, 그 경로 로 가는 길을 모두 Max값 500000 으로 해서 이용 안하게 하고, 최단 거리를 또 구하고 그게 처음 최단 거리와 같으면

또 그 졍로 Max 값 넣고 반복 하다가 만약 다른 최단 거리가 나오면 출력, 만약 가는 길이 없으면 -1 이 나오게 했는데, 문제를 풀고 시간 초과 나오길래...

다른 싸이트에 같은 문제가 있길래 그곳에서 제출 해보았는데 0.11 s 나왔는데 여기에서는 75% 에서 멈추더니 시간 초과 뜨더라구요 ㅜㅜ

이유를 모르겠어요 ㅜㅜ

#include<stdio.h>
#include<vector>
#include<queue>
#pragma warning(disable:4996)
using namespace std;

struct edge{ int end; int cost; };

int main(void)
{
	int N, M;
	int start, end;
	int a, b, c;
	int min;
	queue <edge> que;
	edge e1, e2;
	while (scanf("%d %d", &N, &M) == 2)
	{
		if (N == 0 && M == 0)
			break;
		scanf("%d %d", &start, &end);
		int root[500] = {0,};
		int d[500] = { 0, };
		vector <edge> g[500];
		while (M--)
		{
			scanf("%d %d %d", &a, &b, &c);
			e1.end = b;
			e1.cost = c;
			g[a].push_back(e1);
		}
		for (int i = 0; i < N; i++)
		{
			root[i] = i;
			d[i] = 500000;
		}
		e1.end = start;
		e1.cost = 0;
		d[start] = 0;
		que.push(e1);
		while (!que.empty())
		{
			e1 = que.front();
			que.pop();
			for (int i = 0; i < g[e1.end].size(); i++)
			{
				e2 = g[e1.end][i];
				if (d[e2.end]>e2.cost + e1.cost)
				{
					d[e2.end] = e2.cost + e1.cost;
					e2.cost = e2.cost + e1.cost;
					root[e2.end] = e1.end;
					que.push(e2);
				}
			}
		}
		min = d[end];
		while (min == d[end])
		{
			int k1 = end;
			int k2;
			while (root[k1] != start)
			{
				k2 = root[k1];
				for (int i = 0; i < g[k2].size(); i++)
				{
					if (g[k2][i].end == k1)
					{
						g[k2][i].cost=1000;
					}
				}
				k1 = k2;
			}
			k2 = root[k1];
			for (int i = 0; i < g[k2].size(); i++)
			{
				if (g[k2][i].end == k1)
				{
					g[k2][i].cost = 500000;
				}
			}			
			for (int i = 0; i < N; i++)
			{
				d[i] = 500000;
				root[i] = i;
			}
			e1.end = start;
			e1.cost = 0;
			d[start] = 0;
			que.push(e1);
			while (!que.empty())
			{
				e1 = que.front();
				que.pop();
				for (int i = 0; i < g[e1.end].size(); i++)
				{
					e2 = g[e1.end][i];
					if (d[e2.end]>e2.cost + e1.cost)
					{
						d[e2.end] = e2.cost + e1.cost;
						e2.cost = e2.cost + e1.cost;
						root[e2.end] = e1.end;
						que.push(e2);
					}
				}
			}
		}
		if (d[end] >= 500000)
			printf("-1\n");
		else
			printf("%d\n",d[end]);
	}
}

baekjoon 8년 전 2

시간 초과는 처음에 최단 거리를 찾지 못한 경우에 발생합니다.

첫 번째 다익스트라를 돌린 결과 d[end] = 500000 인 경우입니다.

hj_d 8년 전 0

그럼 처음 최단 거리가 없는 경우 에도 -1 를 출력 하는게 맞는건가요?

oct301 7년 전 0

저도 똑같이 생각해서 풀었더니 틀렸어요 ㅠㅠ

어떤 경로를 공유하고 있는 최단경로가 여러 개 있을 때 그 경로를 모두 못지우는데 그거때문에 틀렸다고 뜨는거 같네여

홧팅

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

문제

문제

출처

ICPC

시간 초과 나는 이유를 알고 싶습니다.

hj_d 8년 전 0

baekjoon 8년 전 2

hj_d 8년 전 0

oct301 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말