글 읽기 - 이게 왜 틀리죠?

jkjan 4년 전 0

https://contest.usaco.org/TESTDATA/FEB07_9.htm

이쪽 거 tc 다 진행해봤는데 다 맞는데 왜 틀린지 모르겠네요.

X부터 시작하는 걸로 그래프를 다익스트라 돌려서 나온 dist 표랑

그 그래프의 역을 돌려서 나온 dist표랑

그 합의 최대값을 구하면 되지 않나요???

출력형식이 틀려서 틀린 건가;;

그래프는 역으로 그리고

가중치 저장하는 map은 또 만들 필요가 없어서

첫째 시행에서 가중치는 A->B로 쓰고

둘째 시행에서는 B->A로 했는데..

tc가 다 맞는데 왜 틀린지 잘 모르겠네요... 혹시 실수가 발견됐다면 좀 도와주세요!!!

#include <stdio.h>
#include <queue>
#include <map>
#include <utility>
#include <vector>

#define INF 1000000000

using namespace std;

class edge{
public:
	int w;
	int v;
	edge(int w, int v) {
		this->w = w;
		this->v = v;
	}
};

struct cmp {
	bool operator ()(edge a, edge b) {
		return a.w > b.w;
	}
};

map<pair<int, int>, int> weight;
int N, M, X;

int* dijkstra(vector<int>*, bool);
vector<int>* reverse(vector<int>*);

int main() {
	int f, t, c;
	int i;
	pair<int, int> e;
	scanf("%d %d %d", &N, &M, &X);

	N++;

	vector<int>* graph = new vector<int>[N];

	for (i = 0; i < M; i++) {
		scanf("%d %d %d", &f, &t, &c);
		e = pair<int, int>(f, t);
		if (weight.count(e) == 0 || (weight.count(e) == 1 && weight[e] > c)) {
			weight[e] = c;
			graph[f].push_back(t);
		}
	}
	
	vector<int>* reversed = reverse(graph);

	int max = 0;
	int sum = 0;
	int path;
	
	int* go = dijkstra(graph, false);
	int* back = dijkstra(reversed, true);

	for (i = 0; i < N; i++) {
		sum = go[i];
		sum += back[i];

		max = max > sum ? max : sum;
	}

	printf("%d", max);

	return 0;
}

int* dijkstra(vector<int>* graph, bool r) {
	int* dist = new int[N];
	pair<int, int> closest;
	pair<int, int> e;
	priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	int i;

	for (i = 1; i < N; i++) {
		if (!r)
			e = pair<int, int>(X, i);
		else
			e = pair<int, int>(i, X);

		dist[i] = (weight.count(e)) ? weight[e] : INF;
		pq.push(pair<int, int>(dist[i], i));
	}

	dist[X] = 0;

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

		for (vector<int>::iterator itor = graph[closest.second].begin(); itor != graph[closest.second].end(); ++itor) {
			if (!r)
				e = pair<int, int>(closest.second, *itor);
			else
				e = pair<int, int>(*itor, closest.second);

			if (dist[*itor] > weight[e] + dist[closest.second]) {
				dist[*itor] = weight[e] + dist[closest.second];
				pq.push(pair<int, int>(dist[*itor], *itor));
			}
		}
	}

	return dist;
}

vector<int>* reverse(vector<int>* graph) {
	vector<int>* reversed = new vector<int>[N];
	int i;
	for (i = 1; i < N; i++) {
		for (vector<int>::iterator itor = graph[i].begin(); itor != graph[i].end(); ++itor) {
			reversed[*itor].push_back(i);
		}
	}
	return reversed;
}

jkjan 4년 전 0

혹시 몰라서 리눅스에 이클립스로 돌려봤더니 웬 이상한 값이.... 이게 왜 이러지;;;;

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

문제

문제

출처

ICPC

이게 왜 틀리죠?

jkjan 4년 전 0

jkjan 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말