코드트리 투어

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

출발지는 통일 되어있다.

처음에는 0으로!

명령어 넣으면

여행 상품의 출발지를 전부 s 로 변경

costid​ 는 현재 여행 상품의 출발지로부터 

id 상품의 도착지 destid​ 까지 도달하기 위한 "최단거리"를 의미합니다.

 

다익스트라다.

출발 노드와 이외의 모든 노드 간의 최단 거리를 구할 때 사용

특징 : 에지는 모두 양수

시간 복잡도 : O(ElogV) - V는 노드 수, E는 에지 수

 

판매 가능한 상품 중 가장 우선순위가 높은 상품을 1개를 판매

-> 연산자 오버로딩  우선순위 큐도 하나 만들어야겠다

 

핵심 조건

1. 두 도시 사이를 연결하는 간선은 여러 개가 존재할 수 있으며,

-> Heap의 크기는 최대 간선 수

2. 자기 자신을 향하는 간선 또한 존재할 수 있습니다.

-> 그래프 만들 때 고려

 

 

<코드>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int q;
int n, m;
 
int start = 0;
 
struct edge {
    int node;
    int weight;
};
 
bool operator < (const edge& a, const edge& b) {
    return a.weight > b.weight;
}
 
vector<edge> mlist[2004];
int mdistance[2004];
bool visited[2004];
 
// greater 해야 최소값 힙, 오름차순 정렬
//priority_queue <edge, vector<edge>, greater<edge>> d_q;
 
// 간선이 여러개 있으므로
// Heap의 최대크기는 간선 개수
edge Heap[10004];
int genzai = 0;
 
void Heap_push(edge data) {
    int idx = ++genzai;
    Heap[idx] = data;
 
    while ((idx != 1) && (Heap[idx / 2] < data)) {
        swap(Heap[idx / 2], Heap[idx]);
        idx = idx / 2;
    }
}
 
edge Heap_pop() {
    edge result = Heap[1];
    Heap[1] = Heap[genzai];
    genzai--;
    
    int parent = 1;
    int child;
 
    while (true) {
        child = parent * 2;
        if (child + 1 <= genzai && Heap[child] < Heap[child + 1])
            child++;
 
        if (child > genzai || Heap[child] < Heap[parent])
            break;
 
        swap(Heap[parent], Heap[child]);
        parent = child;
    }
 
    return result;
}
 
void dijkstra(int hajime)
{
    memset(mdistance, 0x3f, sizeof(mdistance));
    memset(visited, false, sizeof(visited));
 
    Heap_push({ hajime, 0 });
    mdistance[hajime] = 0;
 
    while (genzai != 0)
    {
        edge current = Heap_pop();
        int c_v = current.node;
        if (visited[c_v])
            continue;
        visited[c_v] = true;
 
        for (int i = 0; i < mlist[c_v].size(); i++) {
            int next = mlist[c_v][i].node;
            int weight = mlist[c_v][i].weight;
            if (mdistance[next] > mdistance[c_v] + weight) {
                mdistance[next] = mdistance[c_v] + weight;
                Heap_push({ next, mdistance[next] });
            }
        }
    }
 
}
 
struct info {
    int id;
    int revenue;
    int dest;
    int cost;
};
 
bool dead[30002];
bool made[30002];
 
bool operator < (const info& a, const info& b)
{
    if ((a.revenue - a.cost) == (b.revenue - b.cost))
        return a.id > b.id;
    return (a.revenue - a.cost) < (b.revenue - b.cost);
}
 
priority_queue<info> pq;
 
int sellPackage() {
    while (!pq.empty()) {
        info tmp = pq.top();
        // 최적이라고 생각한 여행 상품이 판매 불가능 하다면 while문을 빠져나가 -1을 반환합니다.
        if ((tmp.revenue - tmp.cost) < 0)
            break;
        pq.pop();
        if (!dead[tmp.id])
            return tmp.id; // 해당 여행 상품이 취소되지 않았다면 정상 판매되므로 id를 반환합니다
    }
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> q;
    while (q--) {
        int query;
        cin >> query;
        if (query == 100) {
            cin >> n >> m;
            int u, v, w;
 
            for (int i = 1; i <= n; i++)
                mlist[i].clear();
 
            for (int i = 0; i < m; i++) {
                cin >> u >> v >> w;
                if (u != v) {
                    mlist[u].push_back({ v, w });
                    mlist[v].push_back({ u, w });
                }
                else
                    mlist[u].push_back({ u, w });
            }
            // 다익스트라
            dijkstra(start);
        }
        else if (query == 200) {
            int id, rev, fin;
            cin >> id >> rev >> fin;
            made[id] = true;
            pq.push({ id, rev, fin, mdistance[fin] });
        }
        else if (query == 300) {
            int c_id;
            cin >> c_id;
            if (made[c_id])
                dead[c_id] = true;
        }
        else if (query == 400) {
            cout << sellPackage() << '\n';
        }
        else if (query == 500) {
            int s;
            cin >> s;
            start = s;
            genzai = 0;
            dijkstra(start);
 
            vector<info> remake;
            // pq에 있던 여행상품들의 정보를 바꾼다
            while (!pq.empty())
            {
                info tmp = pq.top();
                tmp.cost = mdistance[tmp.dest];
                pq.pop();
                remake.push_back(tmp);
            }
 
            for (info p : remake)
                pq.push(p);
        }
    }
    return 0;
}