글 읽기 - 어느 케이스에서 틀렸다고 처리되는건지 못찾겠네여

leekt321 8년 전 0

두 노드 간에 간선이 여러개 있는 것도 고려했고

다익스트라 적용해서 작성했는데 어떤 케이스에서 틀렸다고 나오는지 잘 모르겠습니다.

#include<iostream>
#include<stdio.h>
using namespace std;
int matrix[1001][1001];
bool check[1001];
long long d[1001];
int n;

int extract_min(){
	int idx;
	long long minn=100000001;
	for(int i=1;i<=n;i++){
		if(check[i]==0){
			if(d[i]<minn){
				idx=i;
				minn=d[i];
			}
		}
	}
	return idx;
}
int main(void){
	
	int m;
	int start,end;
	int weight;
	scanf("%d",&n);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			matrix[i][j]=999999;
		}
	}
	scanf("%d",&m);
	for(int i=0;i<=n;i++)
		d[i]=100000000;
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&start,&end,&weight);
		matrix[start][end]=min(weight,matrix[start][end]);
	}
	scanf("%d %d",&start,&end);
	d[start]=0;
	check[start]=1;
	for(int i=1;i<=n;i++){
		if(matrix[start][i]!=999999)
			d[i]=matrix[start][i];
	}
	
	while(1){
		int checkk=0;
		for(int i=1;i<=n;i++)
			if(check[i]==0)
				checkk=1;
		if(checkk==0)
			break;
		int idx=extract_min();
		
		check[idx]=1;
		for(int i=1;i<=n;i++){
			if(matrix[idx][i]!=0)
				d[i]=min(d[i],d[idx]+matrix[idx][i]);
		}
		
		//printf("%d\n", idx);
	}
	printf("%lld\n",d[end]);
}

leekt321 8년 전 1

해결했네요 59번째 라인에 !=0 처리를 !=999999로 바꿔서 해결했습니다.

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

문제

문제

출처

ICPC

어느 케이스에서 틀렸다고 처리되는건지 못찾겠네여

leekt321 8년 전 0

leekt321 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말