백준 9370번 미확인 도착지

백준 9370번 미확인 도착지

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 2000+100
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 187654321;
vector<pii > adj[MAX];
int dist[MAX*2];
bool visited[MAX];
int n, m, t;
int s, g, h;
int cases;
void dijkstra(int start) {
    fill(dist, dist + MAX + 1, INF);
    dist[start] = 0;
    for (int k = 0; k < n; ++k) {
        int here, cost = INF;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] < cost && visited[i] == 0) {
                here = i;
                cost = dist[i];
            }
        }
        visited[here] = 1;
        for (pair<int, int> &p : adj[here]) {
            int there = p.first;
            int there_cost = p.second;
            if (dist[there] > cost + there_cost) {
                dist[there] = cost + there_cost;
            }
        }
    }
}
void dijkstra2(int start, int dest) {
    fill(dist, dist + MAX + 1, INF);
    priority_queue<pii, vector<pii >, greater<pii> > pq;
    pq.push({ start,0 });
    pq.push({ dest, 0 });
    dist[start] = 0;
    dist[dest] = 0;
    while (!pq.empty()) {
        int here = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        if (dist[here] != cost)continue;
        for (pii &p : adj[here]) {
            int there = p.first;
            int new_cost = cost + p.second;
            if (dist[there] > new_cost) {
                dist[there] = new_cost;
                pq.push({ there, new_cost });
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> cases;
    while (cases--) {
        cin >> n >> m >> t;//n은 정점개수, m은 간선개수, t는 후보목적지
        cin >> s >> g >> h; //s는 시작 경로g-h는 필수로 지남.
        int route_gh;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[a].push_back({ b,c });
            adj[b].push_back({ a,c });
            if ((a == g && b == h) || a == h && b == g) route_gh = c; //route_gh는 간선 gh의 길이 
        }
        priority_queue<int, vector<int >, greater<int> > ret;
        for (int i = 0; i < t; i++) {
            int a;
            cin >> a;
            ret.push(a);
        }
        vector<int> ans;
        while (!ret.empty()) {
            memset(visited, 0, sizeof(visited));
            dijkstra(s);            
            int d = ret.top();
            ret.pop();
            int destdist = dist[d];    //s에서 목적지 d까지의 최단 경로길이
            dijkstra2(g, h);      // dist[i] 배열을 정점g,h와 가장 가까운 정점i까지의 길이로 바꿈. 
            if ((destdist) == (dist[s] + route_gh + dist[d])) //s에서목적지 d까지 최단경로길이와
                                                              //1에서 g-h 를 경유하여 목적지d까지 가는 길이가 같은경우
                ans.push_back(d);
        }
        
        for (int i = 0; i <ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
        
        
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
        }
        //간선초기화
    }
    
    return 0;
}

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

문제를 처음접근할때는 직접 경로를 찾아서 해당하는 경우에 출력을 해주는 코딩을 했는데, 

그 방법의 문제점은 최단경로 배열은 같은길이의 여러 최단경로가 있음에도 1가지방법만 저장할 수 있고,

경우의 수가 매우 많아지므로 시간초과까지 났었습니다. 

AC를 받은 방법은 직접 경로를 찾는게 아니라  정점 g,h에서 시작과 끝정점의 최단경로를 찾아서 경로를 계산한것이

시작과 끝정점의 최단경로와 같은 길이 일때, 정답 ans벡터에 추가해주는 방법이였습니다.

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 2000+1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 187654321;
vector<pii > adj[801];
int dist[MAX];
bool visited[MAX];
int parent[MAX];
int n, m, t;
int s, g, h;
int cases;
void dijkstra(int start) {
    fill(dist, dist + n + 1, INF);
    fill(parent, parent + n + 1, 0);
    dist[start] = 0;
    parent[start] = -1;
    for (int k = 0; k < n; ++k) {
        int here, cost = INF;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] < cost && visited[i] == 0) {
                here = i;
                cost = dist[i];
            }
        }
        visited[here] = 1;
        for (pair<int, int> &p : adj[here]) {
            int there = p.first;
            int there_cost = p.second;
            if (dist[there] > cost + there_cost) {
                dist[there] = cost + there_cost;
                parent[there] = here;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> cases;
    while (cases--) {
        memset(visited, 0, sizeof(visited));
        cin >> n >> m >> t;//n은 정점개수, m은 간선개수, t는 후보목적지
        cin >> s >> g >> h; //s는 시작 경로g-h는 필수로 지남.
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[a].push_back({ b,c });
            adj[b].push_back({ a,c });
        }
        priority_queue<int, vector<int >, greater<int> > dest;
        for (int i = 0; i < t; i++) {
            int a;
            cin >> a;
            dest.push(a);
        }
        vector<int> ans;
        dijkstra(s);
        /*
        for (int i = 1; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << endl;
        */
        vector<int> pq;
        while (!dest.empty()) {
            int d = dest.top();
            dest.pop();
            bool Check = false;
            for (int k = d; parent[k] != -1; k = parent[k]) {
                if ((k == g && parent[k] == h) || (k == h && parent[k] == g)) { //경로중에 g-h 또는 h-g로 가는지 확인
                    Check = true;
                    break;
                }
            }
            if (Check) pq.push_back(d);
        }
        for (int i = 0; i < pq.size(); i++)
            cout << pq[i] << " ";
        cout << endl;
        
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
        }
        //간선초기화
    }
    
    return 0;
}

이 코드가 완벽히 잘못접근 했을 때의 코드입니다.