글 읽기 - 교수님은 기다리지 않는다 질문입니다.

waninoko 8년 전 0

처음엔 그냥 bfs로 시작위치부터 끝지점까지 탐색을 했는데 시간초과가 나서 시작 위치와 끝위치를 큐에 넣고 탐색을 했는데 그래도 시간초과가 나더라구요. 제가 무언가 잘못 생각하고 있는건지 아니면 더 좋은 해법이 있는지 궁금합니다

#include <iostream>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <queue>
#pragma warning(disable : 4996)
#define INF 987654321

using namespace std;

vector<vector<pair<int, int> > > graph;
pair<int,int> c[100001];

int sgn(int x) { if (!x) return 0; return x > 0 ? 1 : -1;}
int incr(int x) { if (x < 0) return x - 1; return x + 1;}
long long bfs(int start, int end);
int n, m;

int main() {

	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		
		graph.assign(n + 1, vector<pair<int, int> >());
		for (int i = 0; i < m; i++) {
			char what; int start, end, weight;
			scanf(" %c %d %d", &what, &start, &end);
			switch (what) {
			case '!':
				scanf("%d", &weight);
				graph[start].push_back(make_pair(end, weight));
				graph[end].push_back(make_pair(start, -weight));
				break;
			case '?':
                memset(c, 0, sizeof(c));
                int result = bfs(start, end);
				if (result == INF)
					printf("UNKNOWN\n");
				else printf("%d\n", result);
				
			}
		}
	}

	return 0;
}

long long bfs(int start, int end) {
	if (graph[end].size() == 0) return INF;
	if (start == end) return 0;
    
	queue<pair<int, long long> > q;
	q.push(make_pair(start, 0));
	q.push(make_pair(end, 0));
	c[start].first = 1; c[start].second = 0; c[end].first = -1; c[end].second = 0;
	while (!q.empty()) {
		int here = q.front().first; long long weight = q.front().second;
		q.pop();
		for (int i = 0; i < graph[here].size(); i++) {
			int there = graph[here][i].first;
			if (!c[there].first) {
				q.push(make_pair(there, weight + graph[here][i].second));
				c[there].first = incr(c[here].first);
				c[there].second = weight + graph[here][i].second;
			}
			else if(sgn(c[there].first)!=sgn(c[here].first)){
				int temp;
				if (c[here].first < 0) temp= -c[here].second + c[there].second - graph[here][i].second;
				else temp= c[here].second - c[there].second + graph[here][i].second;
				return temp;

			}
		}
	}
	return INF;
}

kesakiyo 8년 전 1

이 문제는 쿼리가 너무 많아서 단순 bfs를 이용하면 시간초과가 나는 문제에요.

좀 더 효율적인 자료구조를 필요로 합니다.

waninoko 8년 전 0

그렇군요 ㅠㅠ 감사합니다

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

문제

문제

출처

ICPC

교수님은 기다리지 않는다 질문입니다.

waninoko 8년 전 0

kesakiyo 8년 전 1

waninoko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말