글 읽기 - 우선순위큐랑 다익스트라 사용했고, 80%까지 가고 틀렸습니다가 뜹니다..

ael8548 3년 전 0

뭐가 문제일까요...

틀린게 없는 것 같은데 뭐가 틀린건지 잘 모르겠어요 ㅠㅠ

고수님들 도와주세요,,

#include <stdio.h>
#include <queue>
#include<algorithm>
#include <vector>
#include <iostream>
#define INF 99999

using namespace std;
vector<pair<int, int>> g[20001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int mindist[20001] = { 0 };//최단거리
int visited[20001] = { 0 };

void Dijkstra(int s) {
	pq.push(make_pair(0, s));
	while (!pq.empty()) {
		int d = pq.top().first;
		int next = pq.top().second;

		pq.pop();
		visited[next] = 1;

		for (auto i : g[next]) {
			int dochak = i.first;
			int gajung = i.second;

			if (visited[dochak] == 0 && mindist[dochak] > mindist[next] + gajung) {
				mindist[dochak] = mindist[next] + gajung;
				gajung = mindist[dochak];//노드의 가중치로 덮어씌움
				pq.push(make_pair(gajung, dochak));
			}
		}
	}
	return;
}

int main() {
	//v:정점개수, E:간선개수
	int v, E; scanf("%d %d", &v, &E);
	int st; scanf("%d", &st);//시작점

	for (int i = 0; i < E; i++) {
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back(make_pair(b, c));//a-b거리 c
	}

	//초기화
	for (int i = 1; i <= v; i++)
		mindist[i] = INF;
	visited[st] = 1;
	mindist[st] = 0;

	Dijkstra(st);

	for (int i = 1; i <= v; i++) {
		if (mindist[i] == INF) printf("INF\n");
		else printf("%d\n", mindist[i]);
	}
	return 0;
}

rnjstpgns91 3년 전 2

INF가 너무 작습니다. 고쳐주면 통과됩니다.

ael8548 3년 전 0

바로 해결됐어요ㅠㅠㅠㅠㅠㅠㅠ

감사합니다ㅠㅠㅠㅠ!!!

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

문제

문제

출처

ICPC

우선순위큐랑 다익스트라 사용했고, 80%까지 가고 틀렸습니다가 뜹니다..

ael8548 3년 전 0

rnjstpgns91 3년 전 2

ael8548 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말