문제

문제링크 : https://www.acmicpc.net/problem/9370 (단계별로 풀어보기 : 최단경로)

문제 풀이

해당 문제를 풀면서 많은 어려움을 겪었다.. 오랜만에 다익스트라 알고리즘을 구현하는데 애먹었다. 다익스트라 알고리즘은 시작정점에서 이동가능한 정점까지 거리를 체크하고 체크한 값중 가장 작은 값인 정점에서 또 이동가능한 정점까지 거리를 체크해 나가는 방식이다. 구현할때 check값의 최솟값인 인덱스를 계속 찾아줘야함으로 우선순위 큐를 사용하는 것이 좋다. 그렇게 다익스트라 알고리즘은 구현하면된다. 이때 해당 문제는 테스트케이스로 주어짐으로 다음 테스트 케이스에 전의 테스트 케이스가 영향을 주지 못하도록 그래프나 check 등등 초기화를 해줄 필요가 있다. (이 부분에서 시간이 많이 삽질했다.)
주요 문제 풀이는 (s->g + g->h + h->x[i] == s ->x[i]) || (s->h + h->g + g->x[i] == s->x[i]) 이면 그 목적지로 가는 최단거리는 g-h 간선을 포함할 수 있다는 생각이었다. 이생각을 다익스트라 알고리즘을 이용하여 풀면 문제를 해결할 수 있다.
하지만 아래처럼 구현할때 dijstra함수를 많이 call 하고 그에 따라 check 함수도 계속 초기화 해주면서 시간이 꽤나 걸린다. 주요 문제 풀이 생각만 가지고 더 간단하게 구현하면 좋을 것 같다.

알고리즘 스케치

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 2000000000
using namespace std;

typedef struct{
    int v, cost;
}decart;

vector <vector<decart>> graph;
vector <int> x;
int T, n, m, t, s, g, h, a, b, d;

void input();
void dijkstra(int s, int* check);
void sol();

int main()
{   
    fastio;
    cin >> T;
    while(T--){
        input();
        sol();
        for(int i=0; i<n+1; i++)
            graph.erase(graph.begin());
    }
    return 0;
}

void input()
{
    cin >> n >> m >> t;
    cin >> s >> g >> h;
    graph.resize(n+1);
    x.resize(t);
    decart tmp;
    for(int i=0; i<m; i++){
        cin >> a >> b >> d;
        tmp.v = b;
        tmp.cost = d;
        graph[a].push_back(tmp);
        tmp.v = a;
        graph[b].push_back(tmp);
    }
    for(int i=0; i<t; i++){
        cin >> x[i];
    }
}

void dijkstra(int s, int* check)
{
    priority_queue <pair<int,int>> que; // cost, 위치
    int curcost, curindex, nodesize;
    check[s] = 0;
    que.push(make_pair(0,s));
    while(que.size()!=0){
        curcost = -que.top().first;
        curindex = que.top().second;
        que.pop();
        nodesize = graph[curindex].size();
        for(int i=0; i<nodesize; i++){
            if(curcost + graph[curindex][i].cost < check[graph[curindex][i].v]){
                check[graph[curindex][i].v] = curcost + graph[curindex][i].cost;
                que.push(make_pair(-check[graph[curindex][i].v], graph[curindex][i].v));
            }
        }
    }
}

void sol()
{
    vector <int> solution;
    int *check;
    check = new int[n+1];
    for(int i=1; i<=n; i++) check[i]=INF;
    dijkstra(s, check);
    int s1_1 = check[g];
    int s1_2 = check[h];
    int s2;
    int graphgsize = graph[g].size();
    for(int i=0; i<graphgsize; i++){
        if(graph[g][i].v == h){
            s2 = graph[g][i].cost;
            break;
        }
    }
    for(int i=0; i<t; i++){
        for(int i=1; i<=n; i++) check[i]=INF;
        dijkstra(x[i], check);
        int stoe = check[s];
        int s3_1 = check[h];
        int s3_2 = check[g];
        int minvalue = min(s1_1+s2+s3_1, s1_2+s2+s3_2);
        if(minvalue == stoe)
            solution.push_back(x[i]);
    }
    sort(solution.begin(), solution.end());
    int solutionsize = solution.size();
    for(int i=0; i<solutionsize; i++)
        printf("%d ",solution[i]);
    printf("\n");
}