글 읽기 - [c++] 시간초과 관련

gi5005 3년 전 0

시간초과 나는 이유가 있을까요?

#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
#define INF 2147483646
// 트리 DP문제
// 도착지인 정점 2에서 다익스트라를 통해 거리를 구한다.
// 결론적으로 멀어지거나 가까워지거나 하나이기떄문에 방향성이 정해진다.
// 따라서 root부터 트리 생성
// 1에서 부터 시작해서 dp[1] = 1 인접하고 이동할 수 있는 node에 대해서 
// node[next] += dp[pre]
// rec(next);
// answer = dp[2] 
vector<pair<int,int>> E[MAX];
int dst[MAX];
int dp[MAX];
//트리 생성
void mktree(const int &cur,const int &parent)
{
	for(int i=0;i<E[cur].size();i++)
	{
		int nx = E[cur][i].first;
		if(nx == parent) continue;
		if(dst[nx] >= dst[cur]) continue;
		dp[nx] += dp[cur];
		mktree(nx,cur);
	}
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N,M;
	//정점, 간선
	cin >> N >> M;
	//insert
	for(int i=0;i<M;i++)
	{
		int node1 , node2, weight;
		cin >> node1 >> node2 >> weight;
		E[node1].push_back({node2,weight});
		E[node2].push_back({node1,weight});
	}
	//다익스트라 start
	for (int i = 0; i <= N; i++)
	{
		dst[i] = INF;
	}
	priority_queue<pair<int,int>> pq; // weight,cur;
	pq.push({0,2}); // 2에서 부터 시작
	dst[2]=0;
	while(!pq.empty())
	{
		int curW = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if(curW > dst[cur]) continue;
		for(int i=0;i<E[cur].size();i++)
		{
			int nx = E[cur][i].first;
			int nxdist = E[cur][i].second+curW;
			if(dst[nx] > nxdist)
			{
				dst[nx] = nxdist;
				pq.push({-nxdist,nx});
			}
		}
	}
	//end

	//트리 생성
	dp[1]=1;
	mktree(1,-1);
	//정답
	cout << dp[2];

}

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

문제

문제

출처

ICPC

[c++] 시간초과 관련

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말