글 읽기 - 1504 특정한 최단거리 질문입니다.

200924460 8년 전 0

1 -> 2 -> 3 -> 4 로 갈경우

1 -> 3 -> 2 -> 4로 갈경우해서 2가지라고 보고

다익스트라 한번 써서 1 -> 2 , 1 -> 3 을 구해놓고

두번째로 2 -> 3, 2 -> 4를 구하고

마지막으로 3 -> 2, 3 -> 4 인 경우를 구해서 temp1,2에 담은뒤 최소값을 비교해서 출력하였습니다.

길이 없는 경우에는 temp1> 9999 && temp2>9999 , 즉 길이 존재하지 않는다면 dist값이 9999일 거니깐 더해지면 9999를 넘어버리므로, 이렇게 처리해주었습니다.

제가 생각한 TC에서는 잘 돌아가는데 틀렸다고 나오내요.. 어디 부분에서 문제가 생긴걸까요??

감사합니다.

#include <iostream>
#include <stdio.h>
#include <string.h>


using namespace std;

int nodeNum;
int edgeNum;
int arr[900][900];
int dist[1000];
int visit[1000];

void dikstra(int num){

	dist[num]=0;
	int loca;
	int minNum=100000;
	for(int i=0;i<nodeNum;i++){
		minNum=100000;

		for(int j=1;j<=nodeNum;j++){
			if(minNum > dist[j]){
				minNum = dist[j];
				loca = j;

			}

		}

		visit[loca]=1;

		for(int j=1;j<=nodeNum;j++){

			if(dist[j] > dist[loca] + arr[loca][j] && arr[loca][j]!=0){
				dist[j] = dist[loca] + arr[loca][j];
			}

		}
	}

}


int main(){
	
	freopen("input.txt","r",stdin);
	cin>>nodeNum>>edgeNum;
	memset(arr,0,sizeof(arr));	
	for(int i=0;i<edgeNum;i++){
		int xVal;
		int yVal;
		int posVal;
		cin>>xVal>>yVal>>posVal;
		arr[xVal][yVal] = posVal;
		arr[yVal][xVal] = posVal;
	}
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=nodeNum;i++){
		dist[i]=9999;
	}
	//show();

	dikstra(1);

	int temp1=0;
	int temp2=0;

	int end1;//2
	int end2;//3

	cin>>end1>>end2;

	temp1 += dist[end1];
	temp2 += dist[end2];

	memset(visit,0,sizeof(visit));
	for(int i=1;i<=nodeNum;i++){
		dist[i]=9999;
	}

	dikstra(end1);
	temp1+= dist[end2];
	temp2+= dist[nodeNum];

	memset(visit,0,sizeof(visit));
	for(int i=1;i<=nodeNum;i++){
		dist[i]=9999;
	}

	dikstra(end2);
	temp1+= dist[nodeNum];
	temp2+= dist[end1];
	if(temp1 >= 9999 && temp2 >= 9999) {
		cout<<-1<<endl;
		return 0;

	}

	cout<<min(temp1,temp2)<<endl;

	
	return 0;
}

swl2013 8년 전 0

왜 입력 방식이 파일 입출력이죠?

표준 입출력을 사용해 보세요

P.S. TC말고 코드블럭 써보세요

200924460 8년 전 0

ㅇㅏ ..

제출 코드에는 freopen"input.txt","r",stdin); 이거 지우고 냈습니다... visual에서 긁어서 질문 올리는 바람에... 저게 올라갔습니다.. 죄송합니다.

swl2013 8년 전 0

ㅋ 앞으로 조심해주세요

200924460 8년 전 0

아아.. 제출할때는 지우고 냈는데 질문 올리때 저게 올라간에요 ㅠㅠ

아직 해결이 안된거죠...

swl2013 8년 전 0

죄송해요

mmpj 8년 전 0

왔던 길을 여러 번 이용할 수 있어서요..

4 3

1 4 1

2 4 2

3 4 3

2 3

이런 케이스에 답이 11인데 님의 코드로는 경로를 못 찾네요.

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

문제

문제

출처

ICPC

1504 특정한 최단거리 질문입니다.

200924460 8년 전 0

swl2013 8년 전 0

200924460 8년 전 0

swl2013 8년 전 0

200924460 8년 전 0

swl2013 8년 전 0

mmpj 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말