20230808 업다운 랜디

s#100.. !solved_by:p_jun *P5

30분 2문제

 

오늘은 놀아버려서 2문제만 풀었다

 

P5 5551 쇼핑몰 + 2분 6초

문제를 보자마자 다익스트라로 최솟값에서 어떻게 잘하면 될거 같은데...

라는 생각이 들었다

고민하다 거리를 반으로 나누어 두는 방식으로 구현해서 맞았다

그런데 처음 맞은 풀이는 인덱싱 실수를 해서 틀려야 하는데...

데이터가 약한가보다

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 500005;

vector<pair<int, int>> r[3005];

int d[3005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int s, e, w; cin >> s >> e >> w;
        r[s].push_back({ e,w });
        r[e].push_back({ s,w });
    }
    for (int i = 0; i < n; i++) d[i + 1] = INF;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < k; i++) {
        int p; cin >> p;
        d[p] = 0;
        pq.push({ 0,p });
    }
    int ans = 0;
    while (!pq.empty()) {
        int now = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();
        if (d[now] < dist) continue;
        for (auto& [nxt, l] : r[now]) {
            int ndis = dist + l;
            if (ndis < d[nxt]) {
                d[nxt] = ndis;
                pq.push({ -ndis,nxt });
            }
        }
    }
    for (int i = 1; i < n + 1; i++)
        for (auto& [nxt, l] : r[i])
            ans = max(ans, (d[i] + d[nxt] + l + 1) / 2);
    cout << ans << '\n';

}

P4 14433 한조 대기 중 -20분 12초

이분 매칭이란건 바로 알 수 있었다

이분 매칭은 기억이 잘 안나서 찾아 봤다

해결 아이디어는 내가 냈으니 맞은 걸로 ㅎㅎ

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 500005;

vector<int> r[605];
int chk[605], isv[605];

int dfs(int pos) {
    if(isv[pos]) return 0;
    isv[pos] = 1;
    for(int& x: r[pos])
        if (!chk[x] || dfs(chk[x])) {
            chk[x] = pos;
            return 1;
        }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    int k1, k2; cin >> k1 >> k2;
    while (k1--) {
        int i, j; cin >> i >> j;
        r[i].push_back(j);
    }
    while (k2--) {
        int i, j; cin >> i >> j;
        r[i + 300].push_back(j + 300);
    }
    int w = 0, l = 0;
    for (int i = 1; i < n + 1; i++) {
        memset(isv, 0, sizeof(isv));
        if (dfs(i)) w++;
        if (dfs(i + 300)) l++;
    }
    cout << (w < l ? "네 다음 힐딱이" : "그만 알아보자") << '\n';
}