boj 9370 미확인 도착지

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

 

사실 이 문제가 엄청 어려운 문제까진 아니지만

STL 없이 풀만한 좋은 문제라고 생각해서 가져왔다.

리스트, 정렬, 힙, 다익스트라가 알차게 들어가있다.

 

#include <iostream>
#define pii pair<int, int>
using namespace std;
 
pii pq[25000];
int pq_size = 0;
 
void pq_add(int en, int di) // 최소힙
{
    pq[++pq_size] = { en, di };
    int child = pq_size;
    int parent = child / 2;
 
    while (parent >= 1 && pq[parent].second > pq[child].second)
    {
        swap(pq[parent], pq[child]);
        child = parent;
        parent = parent / 2;
    }
}
 
pii pq_pop()
{
    pii t = pq[1];
    pq[1] = pq[pq_size--];
    int parent = 1;
    int child = parent * 2;
 
    while (1)
    {
        if (child + 1 <= pq_size && pq[child].second > pq[child + 1].second)
            child = child + 1;
 
        if (child > pq_size || pq[parent].second <= pq[child].second)
            break;
        swap(pq[parent], pq[child]);
        parent = child;
        child = child * 2;
    }
 
    return t;
}
 
class node
{
public :
    int end;
    int dist;
    node* next;
};
 
 
class Edge
{
public :
    
    node* head = NULL;
    node* tail = NULL;
 
 
    void init()
    {
        node* tmp = head;
 
        while (tmp != NULL)
        {
            head = tmp->next;
            delete tmp;
            tmp = head;
        }
        delete head;
    }
 
 
    void add(int e, int d)
    {
        node* newnode = new node;
        newnode->end = e;
        newnode->dist = d;
        newnode->next = NULL; // 중요
 
        if (head == NULL)
            head = newnode;
        else
            tail->next = newnode;
 
        tail = newnode;
    }
 
 
    void show(int * vector, pii t)
    {
        node* temp = head;
 
        while (temp != NULL)
        {
            int next = temp->end;
            int dist = temp->dist;
 
            if (vector[next] > vector[t.first] + dist)
            {
                vector[next] = vector[t.first] + dist;
                pq_add(next, vector[t.first] + dist);
            }
            temp = temp->next;
 
        }
    }
 
};
Edge edge[2001];
 
int v,e, t, s, g, h;
 
 
 
 
 
void make_dijk(int* vector, int start)
{
    for (int i = 1; i <= v; i++)
    {
        if (i == start)
            vector[i] = 0;
        else
            vector[i] = 987654321;
    }
 
    pq_add( start, 0 );
    while (pq_size != 0)
    {
        pii t = pq_pop();
 
        if (vector[t.first] < t.second)
            continue;
 
        edge[t.first].show(vector, t);
 
    }
 
}
 
void sorting(int *arr, int left, int right)
{
    if (left >= right)
        return;
 
    swap(arr[left], arr[(left + right) / 2]);
 
    int i = left + 1; int j = right;
    int pivot = left;
 
    while (1)
    {
        while (i <= right && arr[i] < arr[pivot])
            i++;
        while (j >= left + 1 && arr[j] > arr[pivot])
            j--;
 
        if (i < j)
            swap(arr[i++], arr[j--]);
        else
            break;
    }
 
 
    swap(arr[pivot], arr[j]);
    sorting(arr, left, j - 1);
    sorting(arr, j + 1, right);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int tc;
    cin >> tc;
    for (int z = 0; z < tc; z++)
    {
        cin >> v >> e >> t >> s >> g >> h;
         
        for (int i = 1; i <= v; i++)
            edge[i].init();
 
        int st, en, di;
 
        int a;
 
        for (int i = 0; i < e; i++)
        {
            cin >> st >> en >> di;
            if ((st == g && en == h) || (st == h && en == g))
                a = di;
 
            edge[st].add(en, di);
            edge[en].add(st, di);
        }
 
        int s_dist[2001];
        int g_dist[2001];
        int h_dist[2001];
 
        make_dijk(s_dist, s);
        make_dijk(g_dist, g);
        make_dijk(h_dist, h);
    
 
        int b;
        int c;
        int ans[1000];
        int ans_size = 0;
        for (int i = 0; i < t; i++)
        {
            cin >> b;
 
            if (s_dist[g] + a + h_dist[b] > s_dist[h] + a + g_dist[b])
                c = s_dist[h] + a + g_dist[b];
            else
                c = s_dist[g] + a + h_dist[b];
 
 
            if (s_dist[b] == c)
                ans[ans_size++] = b;
        }
 
        sorting(ans, 0, ans_size - 1);
 
        //cout << "#" << tc + 1 << " : ";
        for (int i = 0; i < ans_size; i++)
            cout << ans[i] << ' ';
        cout << '\n';
 
 
 
    }
 
}