글 읽기 - 틀렷습니다..

jkjan 4년 전 0

로직은..

그냥 우선순위 큐 다익스트라인데

어디서 틀렸는지 모르겠네요..

비교도 first에 놓고 했고

inf 값도 충분히 주었고

#include <iostream>
#include <set>
#include <queue>
#include <utility>

#define INF 100000000

using namespace std;

set<int> graph[1001];
int distChart[1001][1001];
int* dist;
bool visited[1001];
int from, to;
int N, M;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

void dijkstra();

int main() {
	int depart, arrive, cost;
	int i;

	cin >> N;
	cin >> M;
	N++;

	for (i = 0; i < N; i++) {
		visited[i] = false;
		for (int j = 0; j < N; j++) {
			distChart[i][j] = (i == j) ? 0 : INF;
		}
	}

	for (i = 0; i < M; i++) {
		cin >> depart >> arrive >> cost;
		if (cost < distChart[depart][arrive]) {
			distChart[depart][arrive] = cost;
			graph[depart].insert(arrive);
		}
	}

	cin >> from >> to;

	dist = distChart[from];

	for (i = 1; i < N; i++) {
		pq.push(pair<int, int>(dist[i], i));
	}

	dijkstra();

	cout << distChart[from][to];

	return 0;
}

void dijkstra() {
	pair<int, int> closest;
	pq.pop();

	while (!pq.empty()) {
		closest = pq.top();
		pq.pop();

		for (set<int>::iterator itor = graph[closest.second].begin(); itor != graph[closest.second].end(); ++itor) {
				dist[*itor] = dist[*itor] < dist[closest.second] + distChart[closest.second][*itor] ? dist[*itor] : dist[closest.second] + distChart[closest.second][*itor];
				visited[*itor] = true;
		}
	}
}

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

문제

문제

출처

ICPC

틀렷습니다..

jkjan 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말