9370번 미확인 도착지

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

다익스트라 문제이다.

나는 다익스트라 2번 실행하여 맞췄다.

그러나 더 좋은 풀이가 있었다.

맞춘 후에 jh05013님의 풀이2를 참고하였다.

http://blog.naver.com/PostView.nhn?blogId=jh05013&logNo=220998917105&parentCategoryNo=&categoryNo=124&viewDate=&isShowPopularPosts=true&from=search

g-h 또는 h-g를 반드시 거쳐야하고, 이것들은 최단 거리 중 일부임을 문제에서 보장하였다.

즉, g-h 또는 h-g에 float나 double 형을 선언해주고(예를 들어, 원래 d가 3이라면, 2.9정도),

출발점(s)에서 다익스트라를 실행하여, 목적지 후보들까지

자연수가 나오면(주어진 g-h 또는 h-g가 최단 거리가 아님을 나타냄) 무시하고, 

소수가 나온 것을 출력해주면 된다. 

하지만, 애초에 처음부터 입력할 때 부터 모든 간선의 비용을 2배로 넣어주고(짝수로 만들기 위함),

점선은 2배로 한 뒤 1을 감소시켜주어(홀수로 만들기 위함)

dist가 홀수인 것들만 출력해주면 된다.

홀수라는 것은 g-h 또는 h-g를 거쳐갔다는 증거이다.

또한, 대회 테스트 케이스도 올려본다.

D.in

D.out

다익스트라 2번(내 정답 코드)

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 2002
#define INF 2e9
 
int s, g, h, n, m, t, dist[MAX], dist2[MAX];
 
vector<pair<int, int> > v[MAX];
 
void dijkstra(int start)
{
    priority_queue<pair<int, int> > pq;
 
    dist[start] = 0;
    pq.push({ 0, start });
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
 
        pq.pop();
 
        if (dist[here] < cost) continue;
 
        for (auto i : v[here])
        {
            int next = i.first, next_cost = i.second;
 
            if (dist[next] > dist[here] + next_cost)
            {
                dist[next] = dist[here] + next_cost;
                pq.push({ -dist[next], next });
            }
        }
    }
}
 
void dijkstra2(int start)
{
    priority_queue<pair<int, int> > pq;
 
    dist2[start] = 0;
    pq.push({ 0, start });
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
 
        pq.pop();
 
        if (dist2[here] < cost) continue;
 
        for (auto i : v[here])
        {
            int next = i.first, next_cost = i.second;
 
            if (dist2[next] > dist2[here] + next_cost)
            {
                dist2[next] = dist2[here] + next_cost;
                pq.push({ -dist2[next], next });
            }
        }
    }
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\D.in", "r", stdin);
 
    int test_case, a, b, d;
 
    scanf("%d", &test_case);
 
    for (int tc = 0; tc < test_case; tc++)
    {        
        fill(dist, dist + MAX, INF);
        fill(dist2, dist2 + MAX, INF);
        int candidate, weight, bidx, sidx;
        vector<int> p, temp;
        scanf("%d %d %d %d %d %d", &n, &m, &t, &s, &g, &h);
        for (int i = 0; i <= n; i++) v[i].clear();
 
        for (int i = 0; i < m; i++)
        {
            scanf("%d %d %d", &a, &b, &d);
            if ((a == g && b == h) || (a == h && b == g)) weight = d;
            v[a].push_back({ b, d });
            v[b].push_back({ a, d });
        }
 
        for (int i = 0; i < t; i++)
        {
            scanf("%d", &candidate);
            temp.push_back(candidate);
        }
 
        sort(temp.begin(), temp.end());
 
        dijkstra(s);
 
        if (dist[g] < dist[h]) bidx = h, sidx = g;
        else bidx = g, sidx = h;
        
        dijkstra2(bidx);
 
    //    printf("답 = ");
        for (auto i : temp)
        {
            if (dist[sidx] + weight + dist2[i] <= dist[i])
            {
                printf("%d ", i);
            }
        }
 
        printf("\n");
    }
 
    return 0;
}

짝수, 홀수 활용(jh05013님의 풀이2 참고)

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 2002
#define INF 2e9
 
int s, g, h, n, m, t, dist[MAX];
 
vector<pair<int, int> > v[MAX];
 
void dijkstra(int start)
{
    priority_queue<pair<int, int> > pq;
 
    dist[start] = 0;
    pq.push({ 0, start });
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
 
        pq.pop();
 
        if (dist[here] < cost) continue;
 
        for (auto i : v[here])
        {
            int next = i.first, next_cost = i.second;
 
            if (dist[next] > dist[here] + next_cost)
            {
                dist[next] = dist[here] + next_cost;
                pq.push({ -dist[next], next });
            }
        }
    }
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\D.in", "r", stdin);
 
    int test_case, a, b, d;
 
    scanf("%d", &test_case);
 
    for (int tc = 0; tc < test_case; tc++)
    {        
        fill(dist, dist + MAX, INF);
        int candidate;
        vector<int> p;
        scanf("%d %d %d %d %d %d", &n, &m, &t, &s, &g, &h);
        for (int i = 0; i <= n; i++) v[i].clear();
 
        for (int i = 0; i < m; i++)
        {
            scanf("%d %d %d", &a, &b, &d);
 
            if ((a == g && b == h) || (a == h && b == g))
            {
                v[a].push_back({ b, 2 * d - 1 });
                v[b].push_back({ a, 2 * d - 1 });
            }
            else
            {
                v[a].push_back({ b, 2 * d });
                v[b].push_back({ a, 2 * d });
            }
        }
 
        for (int i = 0; i < t; i++)
        {
            scanf("%d", &candidate);
            p.push_back(candidate);
        }
 
        sort(p.begin(), p.end());
 
        dijkstra(s);
 
        for (auto i : p)
            if ((dist[i] % 2))
                printf("%d ", i);
        
        printf("\n");
    }
 
    return 0;
}