글 읽기 - 다익스트라 ㅠㅠ 틀린 답이라고 합니다

medic_programmer 7년 전 0

일반적인 다익스트라를 짠 것 같은데 틀린 답이라고 합니다 ㅠㅠ

고수님들 도와주시면 감사하겠습니다 ㅠㅠ

#include<queue>
#include<algorithm>
#include<vector>
#include<stdio.h>
#define ME 20001
#define INF 999999999

using namespace std;

int V,E,k,chk[ME];
bool visited[ME];

struct Edge
{
	int to,weight;
};

bool operator <(Edge E1, Edge E2)
{
	return E1.weight > E2.weight;
}


vector<Edge> d[ME];


void input()
{
	int i,u,v,w;
	vector<int>::iterator it;
	Edge p;
	
	scanf("%d%d",&V,&E);
	scanf("%d",&k);
	
	for(i=1; i<=E; i++){
		
		scanf("%d%d%d",&u,&v,&w);
		p.to = v; p.weight = w;
		d[u].push_back(p);
	}
	
}

void dijkstra()
{
	priority_queue<Edge> PQ;
	
	int i,index;
	Edge p;
	
	vector<Edge>::iterator it;
	
	for(i=1; i<=V; i++) chk[i] = INF;
	chk[k] = 0; visited[k] = 1;
	
	//간선이 여러 개 있으면 최솟값을 저장해야 하므로 
	for(it = d[k].begin(); it != d[k].end(); it++){
		if(chk[(*it).to] > (*it).weight) chk[(*it).to] = (*it).weight;
	}
	
	//우선순위 큐에 넣는다 
	for(i=1; i<=V; i++){
		if(chk[i] != INF && chk[i] != 0){
			p.to = i; p.weight = chk[i];
			PQ.push(p);
		}
	}
	
	//다익스트라 
	while(1){
		
		if(PQ.empty() == true) break;
		
		p = PQ.top(); PQ.pop();
		
		index = p.to;
		visited[index] = true;
		
		for(it = d[index].begin(); it != d[index].end(); it++){
			if(visited[(*it).to] == false){
				if((*it).weight + chk[index] < chk[(*it).to]) chk[(*it).to] = (*it).weight + chk[index];
				PQ.push(*it);
			}
		}
	}
	
	
	for(i=1; i<=V; i++){
		if(chk[i] == INF) printf("INF\n");
		else printf("%d\n",chk[i]);
	}
}

int main()
{
	
	input();
	dijkstra();
	
	return 0;
}

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

문제

문제

출처

ICPC

다익스트라 ㅠㅠ 틀린 답이라고 합니다

medic_programmer 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말