글 읽기 - 두 예제 의미는 다 같은거 같은데 하나는 맞고 하나는 시간초과나 나옵니다 ㅠㅠ

goodjaeheui 4년 전 0

다익스트라알고리즘을 썼구요,

하나는 벡터 자체를 리턴시켰고

하나는 distanceq배열을 생성해서 void 리턴형인 다익스트라 함수를 만들어서 했는데

두개다 이것 빼고는 의미가 같은 소스코드인데 백터리턴은 정답이나오고 void함수형은 시간초과가 나는 이유를 잘 모르겠습니다. 교수님들의 조언을 듣고 싶습니다! ㅠㅠ

//예제1
// #b1753 최단경로
#include <iostream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

vector<pair<int, int>> v[20001];
int n, e;
int st_num;

vector<int> bfs(int st,int vertex) {
	vector <int> distance(vertex, INF);
	distance[st] = 0;

	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,st });
	
	//visit[st] = true;
	while (!pq.empty()) {
		int fx = pq.top().second;
		int fw = pq.top().first;
		pq.pop();

		if (distance[fx] < fw) {
			continue;
		}
		

		for (int i = 0; i < v[fx].size(); i++) {
			int nw = fw + v[fx][i].second;
			int nx = v[fx][i].first;
			
			if (distance[nx] > nw) {
				distance[nx] = nw;
				pq.push({ nw,nx });
			}

		}

	}

	return distance;
}

int main() {
	cin >> n >> e;
	cin >> st_num;
	for (int i = 0; i < e; i++) {
		int l, r, w;
		cin >> l >> r >> w;
		v[l].push_back({ r,w });
	}
	vector<int> result=bfs(st_num,n+1);
	for (int i = 1; i <= n; i++) {
		if (result[i] == INF) { cout << "INF" << '\n'; }
		else { cout << result[i] << '\n'; }
	}
}

// 예제 2
// #b1753 최단경로 (다익스트라 예제)
#include <iostream>
#include <vector>
#include <queue>
#define INF 2000000000
using namespace std;

vector <pair<int, int>> v[20001];//정점과 간선에 대한 정보
int d[20001];
int n, m;

void dijkstra(int start) {
	d[start] = 0;
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0,start });

	while (!pq.empty()) {

		int dis=pq.top().first;
		int num = pq.top().second;
		pq.pop();

		if (d[num] < dis)continue;
		for (int i = 0; i < v[num].size(); i++) {
			int ndis = v[num][i].first + dis;
			int nnum = v[num][i].second;
			if (d[nnum] > ndis) {
				d[nnum] = ndis;
				pq.push({ ndis,nnum });
			}
		}

	}
}

int main() {
	cin >> n >> m;
	int start;
	cin >> start;
	for (int i = 0; i < m; i++) {
		int x, y, price;
		cin >> x >> y >> price;
		v[x].push_back({ price,y });
	}
	for (int i = 1; i <= n; i++) {
		d[i] = INF;
	}
	dijkstra(start);

	for (int i = 1; i <= n; i++) {
		if (d[i] == INF)cout << "INF" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

djm03178 4년 전 2

후자는 endl을 썼기 때문입니다. endl은 버퍼를 flush하는 역할을 겸하기 때문에 매우 매우 느립니다.

goodjaeheui 4년 전 0

와.....................해결했습니다 감사합니다........이게 실행속도에 차이를 낼 줄은 생각도 못했습니다.

교수님덕분에 좋은 팁 알고 갑니다 감사합니다 :D

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

문제

문제

출처

ICPC

두 예제 의미는 다 같은거 같은데 하나는 맞고 하나는 시간초과나 나옵니다 ㅠㅠ

goodjaeheui 4년 전 0

djm03178 4년 전 2

goodjaeheui 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말