글 읽기 - 9% 틀립니다.. 무엇이 문제일까요?

ljh3512 1주 전 0

살려주세요.

도와주세요.

											#include<iostream>
#include<queue>
#include<vector>
#include<functional>
#pragma warning(disable:4996)
using namespace std;

int N, M, X;
int mmax = 2147483647;
int mmmax=0;
int a, b, c, i, pos,bef;
int dis;
int cost1[1001]; //1번은 파티하는 곳에서 각 마을까지 계산시 사용
int cost2[1001]; //2번은 각 마을에서 파티하는 곳가지 계산시 사용
int visit1[1001] = { 0, };
int visit2[1001] = { 0, };
vector<pair<int, int>> gr1[1001];
vector<pair<int, int>> gr2[1001];
priority_queue<tuple<int, int, int>, vector<tuple<int, int,int>>, greater<tuple<int, int,int>>> pq;


int main() {
	
	scanf("%d %d %d", &N, &M, &X);

	for (i = 1; i<=N; i++) {
		cost1[i] = mmax;
		cost2[i] = mmax;
	}

	for(i=0;i<M;i++){
		scanf("%d %d %d", &a, &b, &c);
		gr1[a].push_back(make_pair(b, c));
		gr2[b].push_back(make_pair(a, c));
	}

	for (i = 0; i < gr1[X].size(); i++) {
		pq.push(make_tuple(gr1[X][i].second,gr1[X][i].first,X));
	}

	visit1[X] = 1;
	cost1[X] = 0;

	while (!pq.empty()) {
		dis = get<0>(pq.top());
		pos = get<1>(pq.top());
		bef = get<2>(pq.top());
		pq.pop();

		if (cost1[pos] > dis + cost1[bef]) {
			cost1[pos] = dis + cost1[bef];
			if (visit1[pos] == 0) {	
				visit1[pos] = 1;
				for (i = 0; i < gr1[pos].size(); i++) {
					pq.push(make_tuple(gr1[pos][i].second, gr1[pos][i].first, pos));
				}
			}

		}
	}


	for (i = 0; i < gr2[X].size(); i++) {
		pq.push(make_tuple(gr2[X][i].second, gr2[X][i].first, X));
	}

	visit2[X] = 1;
	cost2[X] = 0;

	while (!pq.empty()) {
		dis = get<0>(pq.top());
		pos = get<1>(pq.top());
		bef = get<2>(pq.top());
		pq.pop();

		if (cost2[pos] > dis + cost2[bef]) {
			cost2[pos] = dis + cost2[bef];
			if (visit2[pos] == 0) {
				visit2[pos] = 1;
				for (i = 0; i < gr2[pos].size(); i++) {
					pq.push(make_tuple(gr2[pos][i].second, gr2[pos][i].first, pos));
				}
			}

		}
	}
	
	for (i = 1; i<=N; i++) {
		cost1[i] += cost2[i];
		if (mmmax < cost1[i]) {
			mmmax = cost1[i];
		}
	}

	printf("%d\n", mmmax);
	
	return 0;
}

										

sgchoi5 1주 전 0

usaco 문제는 대회에서 사용했던 TC 가 공개되어 있어서 .. 한 번 해보시길..

http://gooddaytocode.blogspot....

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

문제

문제

출처

ACM-ICPC

9% 틀립니다.. 무엇이 문제일까요?

ljh3512 1주 전 0

sgchoi5 1주 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱