글 읽기 - 왜 시간초과가 날까요?

robin9104 5년 전 0

더미노드 사용해서 다익스트라 2번으로 구하는 코드인데

아무리 봐도 다른 분들하고 큰 차이가 없는 것 같습니다.

왜 시간초과가 날까요..

힌트 부탁드립니다

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

int V, E, M, x, S, y;
vector<pair<int, int>> adj[10001];
priority_queue<pair<int, int>>pq;

void dijkstra(vector<int> &dist)
{
	while (!pq.empty())
	{
		int here = pq.top().first;
		int cost = -pq.top().second;
		pq.pop();
		for (int i = 0; i < adj[here].size(); i++)
		{
			int next = adj[here][i].first;
			int nextdist = cost + adj[here][i].second;
			if (dist[next] > nextdist)
			{
				dist[next] = nextdist;
				pq.push({ next, -nextdist });
			}
		}
	}
}

int main(void)
{
	scanf("%d %d", &V, &E);
	V++;
	for (int i = 0; i < E; i++)
	{
		int start, dest, val;
		scanf("%d %d %d", &start, &dest, &val);
		adj[start].push_back({ dest, val });
		adj[dest].push_back({ start, val });
	}
    //맥세권
	vector<int> dist1(V, 2e9);
	scanf("%d %d", &M, &x);
	for (int i = 0; i < M; i++)
	{
		int temp;
		scanf("%d", &temp);
		dist1[temp] = 0;
		pq.push({ temp, 0 });
	}
	dijkstra(dist1);
    //스세권
	vector<int> dist2(V , 2e9);
	scanf("%d %d", &S, &y);
	for (int i = 0; i < S; i++)
	{
		int temp;
		scanf("%d", &temp);
		dist2[temp] = 0;
		pq.push({ temp, 0 });
	}
	dijkstra(dist2);
    //최소값 계산
	int min = 2e9;
	for (int i = 1; i < V; i++)
		if (dist1[i] && dist2[i] && dist1[i] <= x && dist2[i] <= y)
			min = min < dist1[i] + dist2[i] ? min : dist1[i] + dist2[i];
	if (min == 2e9)
		printf("%d\n", -1);
	else
		printf("%d\n", min);
	return 0;
}

robin9104 5년 전 0

해결했습니다.. priority queue의 첫인자값으로 우선순위가 결정되는걸 몰랐네요

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

문제

문제

출처

ICPC

왜 시간초과가 날까요?

robin9104 5년 전 0

robin9104 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말