글 읽기 - 시간 초과 흠...

200924460 8년 전 0

처음에 dfs로 했다가/ 시간 초과 뜨길래 다익스트라를 공부해서 시도하였습니다. 시간 초과가 뜨더군요.

혹시. 제가 어느 블로그를 참고하여 다익스트라를 구현하였는데, 다익스트라를 잘못 구현한것인지 아니면 다익스트라 말고 다른 알고리즘을 써야하는지요.

ㅁ만약 다른 알고리즘ㅇ르 쓴다면 다익스트라가 안되는 이유는 무엇인지요.

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;


int arr[1010][1010];
int visited[1010][1010];
int nodeNum;
int partyLoca;
int maxLen;
int vertexNum;

void show(){
	for(int i=1;i<=nodeNum;i++){
		for(int j=1;j<=nodeNum;j++){
			cout<<arr[i][j];

		}
		cout<<endl;
	}

}
int tempSum1;
int tempMax;

int dist2To[10000];//각각에서 2로 가는길 저장
int distTo2[10000];//2에서 가는 길 저장.
int visit[10000];

void findLength(int num, int flag){
	if(flag==0){//2에서 가는 경우 저장.
		dist2To[num]=0;
		int loca;
		int minNum=999999;
		for(int i=1;i<=nodeNum;i++){
			minNum=999999;
			for(int j=1;j<=nodeNum;j++){
			if(minNum > dist2To[j] && visit[j]==0){//dist 최소 값 구함
				minNum = dist2To[j];
				loca=j;
			}

		}

			visit[loca]=1;
			for(int j=1;j<=nodeNum;j++){
				if(dist2To[j] > dist2To[loca] + arr[loca][j] && arr[loca][j] != 0)
					dist2To[j] = dist2To[loca] + arr[loca][j];
			}


		}

	}

	else if(flag==1){//다른 node에서 2로 가는 경우
		distTo2[num]=0;
		int loca;
		int minNum=999999;
		for(int i=1;i<=nodeNum;i++){
			minNum=999999;
			for(int j=1;j<=nodeNum;j++){
			if(minNum > distTo2[j] && visit[j]==0){
				minNum = distTo2[j];
				loca=j;
			}

		}

			visit[loca]=1;
			for(int j=1;j<=nodeNum;j++){
				if(distTo2[j] > distTo2[loca] + arr[loca][j] && arr[loca][j] != 0)
					distTo2[j] = distTo2[loca] + arr[loca][j];
			}


		}

	}
}




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

	cin>>nodeNum>>vertexNum>>partyLoca;

	memset(arr,0,sizeof(arr));

	for(int i=1;i<=vertexNum;i++){
		int tempx;
		int tempy;
		int temppos;

		cin>>tempx>>tempy>>temppos;
		arr[tempx][tempy] = temppos;

	}

	//show();

	maxLen=0;
	for(int i=1;i<=nodeNum;i++){
		dist2To[i]=9999;
	}
	findLength(2,0);


	
	for(int i=1;i<=nodeNum;i++){
		
		memset(visit,0,sizeof(visit));
		for(int j=1;j<=nodeNum;j++){
			distTo2[j]=9999;
		}
		int tempSum=0;
		tempSum1=0;
		tempMax=44545611;
		memset(visit,0,sizeof(visit));
		findLength(i,1);//i에서 출발해서 2까지
		tempSum += distTo2[2];
		//cout<<endl;
		//cout<<i<<"To 2 "<<tempSum<<endl;
		tempSum += dist2To[i];
		maxLen = max(maxLen, tempSum);
	}

	
	cout<<maxLen<<endl;
	return 0;
}

skeksk91 8년 전 0

음.. 그냥 제 생각인데

먼저 x도시에서 각 도시로 최단경로를 구합니다. 이때 거리 다 저장하고.

그리고 x도시에서 각 도시로 가는 방향들의 도로를 제거합니다.

그리고 이제 각 도시에서 x로 가는 도로들의 방향을 거꾸로 해주고

x에서 다시 다익스트라를 돌리면 두번만 돌려도 되지않을까 합니다..

문제를 풀어보지 않아서 잘 모르겠지만 맞으면 좋겠습니다~

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

문제

문제

출처

ICPC

시간 초과 흠...

200924460 8년 전 0

skeksk91 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말