글 읽기 - C++ 4%에서 계속 틀립니다..

mintflavoredwater 1년 전 0

반례를 찾아주시거나 이상한 곳을 찾아주신다면 복받으실거에요.. ㅠㅠ

#include <iostream>
#include <vector>
#include <map>
#include <queue>

#define INF 2147483

struct ISD {
	int dst;
	int* cost;

	bool operator<(const ISD& other) const {
		if (cost == other.cost) return dst > other.dst;
		return cost > other.cost;
	}
};

class Graph {
public:
	Graph(int n, int m) : NOV(n) {
		visited = std::vector<bool>(n, false);

		for (int i = 0; i < n; ++i)
			cost[i] = std::map<int, int>();

		for (int i = 0; i < m; ++i) {
			int u, v, w;
			std::cin >> u >> v >> w;
			if (cost[u - 1].find(v - 1) == cost[u - 1].end()) cost[u - 1][v - 1] = w;
			else cost[u - 1][v - 1] = std::min(w, cost[u - 1][v - 1]);
		}
	}

	void solve(int entryPoint) {
		std::vector<int> distance(NOV, INF);
		std::priority_queue<ISD> heap;
		distance[entryPoint] = 0;
		visited[entryPoint] = true;

		for (auto& e : cost[entryPoint])
			distance[e.first] = e.second;

		for (int i = 0; i < NOV; ++i)
			heap.push(ISD{ i, &distance[i] });

		while (!heap.empty()) {
			std::pair<int, int> target;

			if (visited[heap.top().dst]) {
				heap.pop();
				continue;
			}
			else target = std::make_pair(heap.top().dst, *heap.top().cost);

			std::vector<int> detour(NOV, INF);
			detour[target.first] = 0;

			for (auto& e : cost[target.first])
				detour[e.first] = e.second;

			for (int dst = 0; dst < NOV; ++dst)
				if (target.second + detour[dst] < distance[dst]) distance[dst] = target.second + detour[dst];

			visited[target.first] = true;
		}

		for (int e : distance)
			if (e != INF) std::cout << e << '\n';
			else std::cout << "INF" << '\n';
	}

private:
	int NOV;
	std::vector<bool> visited;
	std::map<int, std::map<int, int>> cost;	// cost[src][dst] = distance
};

int main() {
	int theNumberOfVertex, theNumberOfEdge, root;
	std::cin >> theNumberOfVertex >> theNumberOfEdge >> root;
	Graph(theNumberOfVertex, theNumberOfEdge).solve(root - 1);
}

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

문제

문제

출처

ICPC

C++ 4%에서 계속 틀립니다..

mintflavoredwater 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말