글 읽기 - 2번쓴 코드인데 왜 더 느릴까요

phcdream 3년 전 0

다익스트라 2번으로 풀었습니다만, 왜 다른 다익스트라3번 쓴 코드에 비해 시간이 두배넘게 걸릴까요??

다른코드는 60~80ms 인데, 170ms나 걸립니다.

170ms 코드(이 글의 아래 소스코드랑 같음)

24196119번 소스 코드 (acmicpc.net)

다익스트라3번코드

24186969번 소스 코드 (acmicpc.net)

다익스트라3번코드 최근 제출해본 링크

24196258번 소스 코드 (acmicpc.net)

+) 추가로 다익스트라 3번쓴 코드에서는 우선순위큐에서 구해놓은 거리가 더작을경우,

for문 추가로 안돌려도 되는 부분까지 실행하는데도 왜 더느릴까요??

어디서 빼먹은 구현이 있을까요??

/**
 *    BOJ 1504
 *    - 특정한 최단 경로
 *    author:  phcdream
 *    created: 오후 11:11 2020-12-03
**/

#include <iostream>
#include <vector>
#include <queue>

typedef long long ll;

#define INF ((int)1e6+7)

using namespace std;

struct MyStruct
{
	int n;
	int c;
	bool operator<(const MyStruct& ms)const {
		return c < ms.c;
	}
};

int myMin(int a, int b)
{
	return a <= b ? a : b;
}

void in(int& N, int& E, vector<MyStruct>*& graph, int& v1, int& v2)
{
	cin >> N >> E;
	graph = new vector<MyStruct>[(ll)N + 1];
	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(MyStruct({ b,c }));
		graph[b].push_back(MyStruct({ a,c }));
	}
	cin >> v1 >> v2;
}

int* dijkstra(int N, vector<MyStruct>* graph, int v)
{
	priority_queue<MyStruct> pq;
	int* d = new int[(ll)N + 1];
	fill(d, d + N + 1, INF);
	d[v] = 0;
	pq.push(MyStruct({ v,0 }));

	MyStruct st;
	while (true)
	{
		if (pq.empty())
			break;
		st = pq.top();
		pq.pop();
		if (st.c > d[st.n])	// 우선순위큐 값보다 구해놓은 거리값이 더작을경우, continue
			continue;
		for (auto e : graph[st.n])
		{
			if (d[st.n] + e.c < d[e.n])
			{
				d[e.n] = d[st.n] + e.c;
				pq.push(MyStruct({ e.n,d[e.n] }));
			}
		}
	}

	return d;
}

int solve(int N, int E, vector<MyStruct>* graph, int v1, int v2)
{
	int minS = INF;
	int minE = INF;
	int vv;
	int* re = dijkstra(N, graph, v1);	// 정점v1 다익스트라
	minS = re[1];
	minE = re[N];
	vv = re[v2];
	re = dijkstra(N, graph, v2);	// 정점v2 다익스트라

	// S,v1,v2,E 4가지 경우의 수
	int sum;
	int a, b, c, d;
	a = minS + vv + vv + minE;		//	S-v1-v2-v1-E
	b = minS + vv + re[N];			//	S-v1-v2-E
	c = re[1] + vv + minE;			//	S-v2-v1-E
	d = re[1] + vv + vv + re[N];	//	S-v2-v1-v2-E

	sum = myMin(myMin(a, b), myMin(c, d));

	if (sum >= INF)
		return -1;
	else
		return sum;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int N, E;
	vector<MyStruct>* graph;
	int v1, v2;
	in(N, E, graph, v1, v2);

	int re = solve(N, E, graph, v1, v2);
	cout << re << "\n";

	return 0;
}