글 읽기 - 1162 도로포장 문제 시간초과 관련

showme011 6년 전 0

시간초과라는데 어디서 잘못한건지 모르겠네요..

일단

우선순위 큐를 이용해서

현재 위치에서 연결된 간선을 보면서

포장할때, 안할때 구분해서 했는데

시간초과 나네요 ㅠㅠ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define min(a,b)	( (a) < (b) ? (a) : (b) )

struct Edge
{
	int to;
	int cost;
};

int N , M , K;
vector<Edge> edge[10001];			int d[10001][21];

void init()
{
	memset(d , 0x3f , sizeof(d));

	scanf("%d %d %d" , &N , &M , &K);

	int u , v , c;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d" , &u , &v , &c);
		edge[u].push_back({v,c});
		edge[v].push_back({u,c});
	}
}

void solve()
{
	int result = 0x3f3f3f3f;
	priority_queue<pair<int , pair<int , int > > > q;					// 거리   위치   포장 횟수

	for (int i = 0; i <= K; i++)
		d[1][i] = 0;
	
	q.push({0,{1,0}});

	while (!q.empty())
	{
		int cost = q.top().first;										//시간 
		int here = q.top().second.first;								//현재위치
		int wraped = q.top().second.second;								//포장 횟수
		q.pop();

		if (d[here][wraped] < cost)
			continue;

		int size = edge[here].size();

		for (int i = 0; i < size; i++)
		{
			int there = edge[here][i].to;								//이동하려는 위치
			int there_cost = edge[here][i].cost + cost;					//이동하는데 걸리는 시간


			if (wraped < K && cost < d[there][wraped + 1])				//포장한횟수가 K보다 작을때
			{
				q.push({cost , {there,wraped + 1}});
				d[there][wraped + 1] = cost;
			}

			if (there_cost < d[there][wraped])							//아닐때
			{
				q.push({there_cost,{there,wraped}});
				d[there][wraped] = there_cost;
			}
		}
	}

	for (int i = 0; i <= K; i++)										//도착지까지의 최소시간 찾기 
		result = min(result , d[N][i]);

	printf("%d\n" , result);
}

int main()
{
	init();

	solve();

	return 0;
}

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

문제

문제

출처

ICPC

1162 도로포장 문제 시간초과 관련

showme011 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말