🖊️ 문제

https://www.acmicpc.net/problem/17396

---

🖊️ 풀이

가중치가 있는 그래프의 최소 시간?
Dijkstra로 기릿

일단,,
상대의 시야에 보이는지 여부를 bool로 받아서 visited배열로 담아 두고, 다익스트라 진행하면서 갈 수 없다면 빼줬다.

근데 시간초과났다.

아래는 시간초과난 코드.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct compare {
	bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
		return a.second > b.second;
	}
};

int n, m;
bool visitable[100'001];
int cost[100'001];
// idx, cost
vector<pair<int, int>> vec[100'001];
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;

void Dijkstra()
{
	pq.push(make_pair(0, 0));
	cost[0] = 0;
	while (!pq.empty()) {
		int cur = pq.top().first;
		int curCost = pq.top().second;
		pq.pop();
		if (curCost > cost[cur]) continue;
		
		for (auto& v : vec[cur]) {
			int next = v.first;
			int nextCost = curCost + v.second;
			if (visitable[next] && next != n - 1) continue;
			if (cost[next] < nextCost) continue;
			cost[next] = nextCost;
			pq.push(make_pair(next, nextCost));
		}
	}
	if (cost[n - 1] == 987654321) cost[n - 1] = -1;
	cout << cost[n - 1] << endl;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	bool flag;
	for (int i = 0; i < n; i++) {
		cin >> flag;
		visitable[i] = flag;
		cost[i] = 987654321;
	}

	int a, b, t;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> t;
		vec[a].emplace_back(make_pair(b, t));
		vec[b].emplace_back(make_pair(a, t));
	}

	Dijkstra();
}

아니..
이거 진짜 오래풀었다

https://music.youtube.com/watch?v=PYq5hsjigdc&si=z-TJfMaBtyk07PBx

해결할때까지 백도어만 들음 화난다;;

갑자기 시간초과? 여기서??

1. priority_queue에서 연산자 오버로딩
2. pq에서 first, second 순서 변경
3. pq.top()연산 줄이고자 top받아다가 연산

등.. 을 고려해봤다

근데 진짜 충격적인것..

if - continue를 제거하고, if문으로 냅다 감싸줬더니 시간초과가 해결됐다..

아무래도,,
이미 if문이 끝난 상황에서 continue를 사용해서 오버헤드 나는 것 보다는,
그냥 괄호로 감싸서 수행하는게 나을 것 같다.
특히 위 코드같은 경우에..

문제 자체는 20분만에 풀었는데
저 continue때문에.. 내 2시간......

되게 어이없지만..
그래도 내 습관 고치려면 꼭 필요했던 순간이었겠지....

이제 백도어 탈출이다 진짜 하

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

struct compare {
	bool operator() (const pair<int, ll>& a, const pair<int, ll>& b) const {
		return a.second > b.second;
	}
};

ll INF = 10'000'000'000'000;

int n, m;
bool visitable[100'001];
ll cost[100'001];
// idx, cost
vector<pair<int, ll>> vec[100'001];
priority_queue<pair<int, ll>, vector<pair<int, ll>>, compare> pq;

void Dijkstra()
{
	pq.push(make_pair(0, 0));
	cost[0] = 0;
	while (!pq.empty()) {
		int cur = pq.top().first;
		ll curCost = pq.top().second;
		pq.pop();
		if (cur == n - 1) break;
		if (curCost > cost[cur]) continue;
		
		for (auto& v : vec[cur]) {
			int next = v.first;
			ll nextCost = curCost + v.second;
			// if (cost[next] < nextCost) continue;
			if (nextCost < cost[next]) {
				cost[next] = nextCost;
				pq.push(make_pair(next, nextCost));
			}
		}
	}
	if (cost[n - 1] == INF) cout << -1 << '\n';
	else cout << cost[n - 1] << '\n';
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> visitable[i];
		cost[i] = INF;
	}

	int a, b, t;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> t;
		//if ((visitable[a] && a != n-1) || (visitable[b] && b != n-1)) continue;
		if ((!visitable[a] && !visitable[b]) || (a == n - 1 || b == n - 1)) {
			vec[a].emplace_back(make_pair(b, t));
			vec[b].emplace_back(make_pair(a, t));
		}
	}

	Dijkstra();
}