[C++] Dijkstra Algorithm / codeforces-449-B

https://codeforces.com/contest/449/problem/B

Problem - B - Codeforces

---

#include <bits/stdc++.h>
using namespace std;

class tpl {
public:
	int b, w, isT;
};

vector <tpl> ED[300005];

long long SL[300005];
int ENU[300005];
int ELE[300005];
int visited[30005] = {0};

int n, m, k;

class pkt {
public:
	long long l;
	int a, b, w, isT;
};

struct comp {
	bool operator()(pkt A, pkt B) {
		if (A.l > B.l)
			return true;
		else if (A.l == B.l)
			return A.isT > B.isT;
		return false;
	}
};

priority_queue<pkt, vector<pkt>, comp> pq;

void Dij(int s)
{
	pkt p, q; int i;
	p.l = 0; p.a = 0;  p.b = s; p.w = 0;  p.isT = 0;
	pq.push(p);

	while (!pq.empty())
	{
		p = pq.top();	pq.pop();
		//cout << "* 노드 [ " << p.b << " ] 꺼냈다." << endl;
		if (visited[p.b]) {
			//cout << "** 노드 [ " << p.b << " ]는 이미 방문했다" << endl;
			continue;
		}
		visited[p.b] = 1;	SL[p.b] = p.l;	ENU[p.b] = p.isT;
		for (i = 0; i < ED[p.b].size(); i++)
		{
			q.l = SL[p.b] + ED[p.b][i].w;
			q.w = ED[p.b][i].w;
			q.a = p.b;
			q.b = ED[p.b][i].b;
			q.isT = ED[p.b][i].isT;
			pq.push(q);
			//cout << "방금 노드 [ " << q.b << " ] 큐에 들어갔다 (끝)" << " --- l은 : " << q.l << " 기차 타나 ? "<< q.isT <<"  현재 Q에는 : " << pq.size() << endl;
		}
	}
}

int main()
{
	int i, x, y, W;
	int ans, cnt = 0;
	tpl tmp;
	cin >> n >> m >> k;

	for (i = 1; i <= m; i++) {
		cin >> x >> y >> W;
		tmp.b = y; tmp.w = W; tmp.isT = 0; ED[x].push_back(tmp);
		tmp.b = x; tmp.w = W; tmp.isT = 0; ED[y].push_back(tmp);
	}
	for (i = 1; i <= k; i++) {
		cin >> y >> W;
		tmp.b = y; tmp.w = W; tmp.isT = 1; ED[1].push_back(tmp);
		//tmp.b = 1; tmp.w = W; tmp.isT = 1; ED[y].push_back(tmp);
	}

	Dij(1);
	for (i = 1; i <= n; i++)
	{
		// 기찻길이 사용된 경우
		if (ENU[i] == 1)
			cnt++;
	}

	ans = k - cnt;
	cout << ans << '\n';

	return 0;
}

---

우선순위 큐에 넣은 pkt들의 우선 순위를 연산자 오버로딩 하는 방식 확인하기.