inwooleeme
๋์ด ์๋ ค์ค ๋ฐ์ง ๊ทธ๋ํ์์์ ๊ทธ๋ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฐฉ๋ฒ. ๊ด๋ จ ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ํ์ธํด๋ณด์.
์๋ ๋ธ๋ก๊ทธ ๊ธ๋ ๋ง์ด ์ฐธ๊ณ ๋์๋ค.
๋ชจ๋ ๊ฐ์ ์ ๊ธธ์ด๊ฐ ๋์ผํ๋ฏ๋ก, queue๋ฅผ ์จ์ ํ์ด๋ณด์. ์ด๊ธฐ์ ์์ ์ ์ ์ ์ง์ด๋ฃ๊ณ , ์ฐ๊ฒฐ๋ edge๋ฅผ ์ํํ๋ ์ง๊ทนํ ํ๋ฒํ bfs ์ด๋ค. ์๊ฐ๋ณต์ก๋๋ ์ด๊ณ , ๋ฐ์ง ๊ทธ๋ํ์์๋ ์ด๋ฏ๋ก ์ ๊ฐ๊น๊ฒ ๋๋ค.
vector<bool> vis;vis.resize(N, false);queue<pair<int,int>> q; // ๊ฐ์ ๊ธธ์ด๊ฐ ๊ฐ์ผ๋ฏ๋ก pq ์ฐ๋๊ฑฐ๋ q ์ฐ๋๊ฑฐ๋ ๋๊ฐ๋ค.q.push({0, 0}); // vertex, distll ans1 = INF;while(q.size()) {auto cur = q.front(); q.pop();if (cur.first == N - 1) {ans1 = (ll)cur.second * A;break;}vis[cur.first] = true;for(auto& nxt: e[cur.first]) {if (vis[nxt]) continue;q.push({nxt, cur.second + 1});}}
์ด ๋ถ๋ถ์ด ๋ค๋ฃจ๊ณ ์ ํ๋ ๋ถ๋ถ์ธ๋ฐ, ๋ฐ์ง ๊ทธ๋ํ์ ๊ฒฝ์ฐ ์ง๊ด์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์ ์ queue์ ๊ณ์ ๋ฃ๋ ๊ฒ์ ๋ฐ๋ณตํ๊ฒ ๋ ๊ฒฝ์ฐ์๋ ๊ฐ์ ์ ์ ์ด ๋ฐ๋ณตํด์ ๊ณ์ ๋ค์ด๊ฐ๊ฒ ๋ ๊ฒ์ด๋ค. ๋ง์ฝ SPFA
์ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ํ์ฉํ๊ณ ์ ํ๋๋ผ๋, ์ ์ ์ด ๋น ์ง ์๊ฐ์ ๋์ ํ๋ฅ ๋ก ๋ค์ queue์ ๋ค์ด๊ฐ๊ฒ ๋๋ฏ๋ก ์ํ์๊ฐ์ ์ค์ด๋ค๋๋ผ๋ ์ ์ฒด์ ์ธ ์๊ฐ๋ณต์ก๋๋ ํฌ๊ฒ ์ค์ด๋ค๊ธฐ ์ด๋ ต๋ค. ๋ฐ๋ผ์ ์๋์ ๊ฐ์ ๋ฐฉ์์ฒ๋ผ unvisited
set์ ํ๋ ๋ง๋ค์ด๋๊ณ , unvisited
์ ์ ์ ์ ํ๋์ฉ ๋นผ๋ฉด์ queue์ ๋ฃ๋ ๋ฐฉ์์ด ์ ํจํ๋ค. ๋ฌผ๋ก dense
ํ๋ค๊ณ ํ๋๋ผ๋, ๋ชจ๋ ์ ์ ์ด ์ฐ๊ฒฐ๋์๋ค๋ ์ด์ผ๊ธฐ๋ ์๋๋ฏ๋ก, ์ด๋ถ ํ์์ ํ์ฉํด์ ์ค์ ๋ก ์ด์ด์ง ์ ์ ์ธ์ง ํ์ธํด์ผ ํ๋ค. ์ด๋ถ ํ์์ ํ ๋ฒ ์ฌ์ฉํ๋๋ฐ์ ์ ์๋ณต๋๊ฐ ๊ฑธ๋ฆฌ๊ณ , ์ ์์ ๊ทธ๋ํ์์ ๋น ์ง ๊ฐ์ ์ ์(dense graph์์๋ ์์ ์์ผ ๊ฒ์ด๋ค)๋ก ์ ์ํ๋ฉด ์ด ๋งํผ ์ด๋ถ ํ์์ด ๋ฐ๋ณต๋๋ฏ๋ก ์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
๊ทธ๋ฆฌ๊ณ , ๋ค๋ฅธ ๊ด์ ์์ ๋ชจ๋ ์ ์ ์ด unvisited
๋ก๋ถํฐ ํ๋ฒ์ฉ ๋น ์ง๊ฒ ๋๋ฏ๋ก, ์ ์๋ณต๋๊ฐ ๊ฑธ๋ฆฐ๋ค. ์ด๋ฅผ ์ข
ํฉํ๋ฉด, ์ ์ฒด์ ์ธ ์๊ฐ๋ณต์ก๋๋ ์ด๋ค. ์ผ๋ฐ์ ์ธ BFS ์๋ณต๋์ธ ์ ๋นํด ๋ง์ ๊ฐ์ ์ด ์๋ค๊ณ ํ๊ฒ ๋ค.
set<int> unvis;FOR(i,1,N) unvis.insert(i);q = {};q.push({0, 0}); // vertex, distll ans2 = INF;while(q.size()) {auto cur = q.front(); q.pop();if (cur.first == N - 1) { // ์ฌ๊ธฐ๊น์ง ๊ฐ์ans2 = (ll)cur.second * B;break;}// cur์ ์ด์ด์ง ๊ฐ์ ์ ๋ณด๋ ๋์ ์, unvis ์ค์์ ํ๋๋ฅผ ๋ณธ๋ค. (dense ํ๋ฏ๋ก ๋๋ถ๋ถ์ ๊ฒฝ์ฐ ๊ฒฝ๋ก๊ฐ ์๋ค)for(auto it = unvis.begin(); it != unvis.end(); ) {int nxt = *it;if (e[cur.first].find(nxt) == e[cur.first].end()) {// ์์ง ๋ฐฉ๋ฌธ ์ํ ์ ์ ์ด๋ค.q.push({nxt, cur.second + 1});it = unvis.erase(it);} else {++it;}}}