글 읽기 - 어떤 케이스에서 틀리는지 모르겠습니다.

janghoy100 7년 전 1

예제 케이스랑 제가 만든 간단한 케이스 내에서는 맞게 나오는데 채점할 때는 틀리다고 나옵니다.

혹시 엄밀한 케이스가 있다면 도움주시면 감사하겠습니다. ㅠㅠ

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>

#define INF 99999999

using namespace std;

vector<pair<int, int>> adj[500];
int trace[500];

int v;
vector<int> dijkstra(int src) {
	vector<int> dist(v,INF);
	dist[src] = 0;
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, src));
	while (!pq.empty()) {
		int cost = pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				trace[there] = here;
				pq.push(make_pair(nextDist, there));
			}
		}
	}
	return dist;
}

int main() {
	int e, s, d;
	int i,to,from;
	int a, b, w;
	int firstvalue, nextvalue;
	vector<int> result;
	freopen("input.txt", "r", stdin);
	while (1) {
		for (i = 0; i < 500; i++) adj[i].clear();
		for (i = 0; i < 500; i++) trace[i] = INF;
		scanf("%d %d",&v,&e);
		if (!v && !e) break;
		scanf("%d %d", &s,&d);
		for (i = 0; i < e; i++) {
			scanf("%d %d %d", &a, &b, &w);
			adj[a].push_back(make_pair(b, w));
		}
		result = dijkstra(s);
		firstvalue = result[d];
		
		if (firstvalue != INF) {
			do {
				to = d;
				while (to != s) {
					from = trace[to];
					for (i = 0; i < adj[from].size(); i++) {
						if (adj[from][i].first == to) {
							adj[from][i].second = INF;
							//벡터 안의 내용 지우기 내일 구현
						}
					}
					to = from;
				}
				for (i = 0; i < 500; i++) trace[i] = INF;
				result = dijkstra(s);
				nextvalue = result[d];
			} while (firstvalue == nextvalue);
			if (nextvalue == INF) printf("-1\n");
			else printf("%d\n", nextvalue);
		}
		else printf("-1\n");
	}

	return 0;
}

sgchoi5 7년 전 2

http://gooddaytocode.blogspot.... 참고하시길..... TC 는 있어요....

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

문제

문제

출처

ICPC

어떤 케이스에서 틀리는지 모르겠습니다.

janghoy100 7년 전 1

sgchoi5 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말