글 읽기 - 다익스트라 TLE

pianosiwon 2년 전 0

PQ로 풀었는데 시간초과가 나용 ㅠ

고수님들 도와주세요

#include <iostream>
#include <queue>
#include <vector>
#define INF 210000000
using namespace std;
vector<pair<int,int>>v[20002];
int d[20002];
int N, E,S;
struct compare {
	bool operator()(pair<int, int>a, pair<int, int>b) {
		return a.second < b.second;
	}
};
priority_queue<pair<int, int>,vector<pair<int,int>>,compare>q;
void BFS()
{
	d[S] = 0;
	q.push({ S,0 });
	while (!q.empty())
	{
		int node = q.top().first;
		int dist = q.top().second;
		q.pop();
		if (d[node] < dist) continue;
		for (int i = 0; i < v[node].size(); i++)
		{
			int next = v[node][i].first;
			int nextdist = dist + v[node][i].second;
			if (nextdist < d[next])
			{
				d[next] = nextdist;
				q.push({ next,nextdist });
			}
		}
	}

}

int main()
{
	cin >> N >> E >> S;
	for (int i = 0; i <= N; i++) d[i] = INF;
	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	BFS();
	for (int i = 1; i <= N; i++)
	{
		if (d[i] == INF) cout << "INF\n";
		else cout << d[i] << '\n';
	}

}

djm03178 2년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

다익스트라 TLE

pianosiwon 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말