글 읽기 - 아래 소스가 왜 틀렸을까요 (소스 간단함)

dnjsdudals32 6년 전 0

1초도 안돼서 틀리네요 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

class Edge {
public:
	int u, v, w;

	Edge(int u, int v, int w) {
		this->u = u;
		this->v = v;
		this->w = w;
	}

	bool operator< (const Edge& other) const {
		return this->w < other.w;
	}

	bool operator> (const Edge& other) const {
		return this->w > other.w;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int v, e, k, dist[20001];
	vector<vector<Edge>> ve;
	priority_queue<Edge, vector<Edge>, greater<Edge>> que;

	cin >> v >> e >> k;
	ve.resize(v + 1);
	for (int i = 0; i < e; i++) {
		int u, v, w;

		cin >> u >> v >> w;
		ve[u].push_back({ u, v, w });
	}

	for (int i = 1; i <= v; i++) {
		dist[i] = -1;
	}

	que.push({ k, k, 0 });
	while (!que.empty()) {
		Edge next = que.top();
		que.pop();

		if (dist[next.v] > next.w || dist[next.v] == -1) {
			dist[next.v] = next.w;

			for (Edge temp : ve[next.v]) {
				temp.w += dist[next.v];
				que.push(temp);
			}
		}
	}

	cout << 0 << "\n";
	for (int i = 1; i <= v; i++) {
		if (i == k)continue;
		if (dist[i] == -1) {
			cout << "INF\n";
		}
		else {
			cout << dist[i] << "\n";
		}
	}
}

yapy 6년 전 1

시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

인데 무조건 0부터 출력하시네요.

dnjsdudals32 6년 전 0

그래서 고쳐봤는데 그래도 틀렸네요 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

class Edge {
public:
	int vertex, weight;

	Edge(int vertex, int weight) {
		this->vertex = vertex;
		this->weight = weight;
	}

	bool operator> (const Edge& other) const {
		return this->weight > other.weight;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int v, e, k, dist[20001];
	vector<vector<Edge>> ve;
	priority_queue<Edge, vector<Edge>, greater<Edge>> que;

	cin >> v >> e >> k;
	ve.resize(v + 1);

	for (int i = 0; i < v; i++) {
		int u, v, w;

		cin >> u >> v >> w;
		ve[u].push_back({ v, w });
	}

	for (int i = 1; i <= v; i++) {
		dist[i] = INT32_MAX;
	}

	que.push({ k,0 });
	while (!que.empty()) {
		Edge now = que.top();
		que.pop();

		if (now.weight < dist[now.vertex]) {
			dist[now.vertex] = now.weight;

			for (Edge pos : ve[now.vertex]) {
				pos.weight += dist[now.vertex];
				que.push(pos);
			}
		}
	}

	dist[k] = 0;
	for (int i = 1; i <= v; i++) {
		if (dist[i] == INT32_MAX) {
			cout << "INF\n";
		}
		else {
			cout << dist[i] << "\n";
		}
	}
}

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

문제

문제

출처

ICPC

아래 소스가 왜 틀렸을까요 (소스 간단함)

dnjsdudals32 6년 전 0

yapy 6년 전 1

dnjsdudals32 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말