[c++] 백준 10217 - KCM Travel(현재 풀이중)

0. [c++] 백준  -

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

1. 풀이

triple을 사용하려다 pair을 활용하였고, 지금 벨만-포드로 구현을 하고 있었는데, 시간을 기준으로 정렬을 해주려다가, 코스트에 따른 배열도 마련을 해주어야 할 것 같아서 우선 보류를 해주었다.

2차 시도....

왜 다 맞은걸로 보이는데 틀리는거지?

음........

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150

#include<iostream> #include<vector> #include<queue>   using namespace std;   //triple에 대한 출처 //https://hugman.tistory.com/entry/C-stdtriple //http://www.bioinf.uni-leipzig.de/Software/bbq/doc/structstd_1_1triple.html #ifndef __GLIBCPP_INTERNAL_TRIPLE_H #define __GLIBCPP_INTERNAL_TRIPLE_H   namespace std {       template <class _T1, class _T2, class _T3>     struct triple {         typedef _T1 first_type;         typedef _T2 second_type;         typedef _T3 third_type;           _T1 first;         _T2 second;         _T3 third; #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS         //265.  std::triple::triple() effects overly restrictive         triple() : first(), second(), third() {} #else         triple() : first(_T1()), second(_T2()), third(_T3()) {} #endif           triple(const _T1& __a, const _T2& __b, const _T3& __c) : first(__a), second(__b), third(__c) {}           template <class _U1, class _U2, class _U3>         triple(const triple<_U1, _U2, _U3>& __p) : first(__p.first), second(__p.second), third(__p.third) {}     };       template <class _T1, class _T2, class _T3>     inline bool operator==(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y)     {         return __x.first == __y.first && __x.second == __y.second && __x.third == __y.third;     }       template <class _T1, class _T2, class _T3>     inline bool operator<(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y)     {         return __x.first < __y.first ||             (!(__y.first < __x.first) && __x.second < __y.second) ||             ((!(__y.first < __x.first) && !(__y.second < __x.second) && __x.third < __y.third));     }       template <class _T1, class _T2, class _T3>     inline bool operator!=(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y) {         return !(__x == __y);     }       template <class _T1, class _T2, class _T3>     inline bool operator>(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y) {         return __y < __x;     }       template <class _T1, class _T2, class _T3>     inline bool operator<=(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y) {         return !(__y < __x);     }       template <class _T1, class _T2, class _T3>     inline bool operator>=(const triple<_T1, _T2, _T3>& __x, const triple<_T1, _T2, _T3>& __y) {         return !(__x < __y);     }       template <class _T1, class _T2, class _T3> #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS     //181.  make_triple() unintended behavior     inline triple<_T1, _T2, _T3> make_triple(_T1 __x, _T2 __y, _T3 __z) #else     inline triple<_T1, _T2, _T3> make_triple(const _T1& __x, const _T2& __y, const _T3& __z) #endif     {         return triple<_T1, _T2, _T3>(__x, __y, __z);     }   } // namespace std   #endif /* __GLIBCPP_INTERNAL_TRIPLE_H */   const int INF = 1000000007; const int MAX_N = 101;     //first는 다음 공항, second.first는 cost, second.second는 소요 시간이다. vector<pair<int, pair<int, int> > > adj[MAX_N];   //벨만-포드 알고리즘을 활용한 탐색 void bellmanFord(int N) {     //앞은 소요시간을 저장하고, 뒤는 비용을 저장한다.     vector<pair<int, int> > upper(N + 1, { INF, 0 });     //1에서 시작하므로 1은 0으로 한다.     upper[1] = { 0,0 };          bool updated = false;       for (int iter = 0; iter < N; iter++) {         updated = false;         for (int here = 1; here <= N; here++) {             int thisCost = 0;             for (int i = 0; i < adj[here].size(); i++) {                 int there = adj[here][i].first;                 int cost = adj[here][i].second.first;                 int timeCost = adj[here][i].second.second;                 if (upper[there].first > upper[here].first + timeCost) {                     thisCost = cost;                     upper[there].first = upper[here].first + timeCost;                 }             }         }              }     }           //다익스트라 알고리즘을 활용한 탐색 void dijkstra(int N) {         priority_queue<pair<int, int> > pq;     pq.push(adj[1]); }   int main() {     int T, N, M, K;     int start, end, cost, timeDelay;     cin >> T;     while (T--) {         cin >> N >> M >> K;         adj->clear();         for (int i = 0; i < K; i++) {             cin >> start >> end >> cost >> timeDelay;             adj[start].push_back({ end, {cost, timeDelay} });         }     }         return 0; } Colored by Color Scripter

cs

2차 시도

#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
 
using namespace std;
 
//순서대로 도착공항, 비용, 소요시간
vector<tuple<int, int, int> > adj[101];
//dist[i][j] : 1번 도시에서 i번 도시까지 비용 j를 사용하는 최소 시간
int dist[103][10003];
const int INF = 1000000007;
 
//N개의 도시와 M원의 지원비용으로 N번 공항을 갈 수 있는지 확인하자.
void dijkstra(int N, int M) {
    //초기화
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            dist[i][j] = INF;
    //출발 도시는 1번 이므로 초기값을 넣어준다.
    dist[1][0] = 0;
    //순서대로 -소요시간, 비용, 현재 위치이다.
    priority_queue<tuple<int, int, int> > pq;
    pq.push({ 0,1,0 });
    while (!pq.empty()) {
        int hereTimeCost = -get<0>(pq.top());
        int here = get<1>(pq.top());
        int hereCost = get<2>(pq.top());
        pq.pop();
        //만일 도착하였다면, 소요시간을 출력한다. 그리고 종료
        if (here == N) {
            cout << hereTimeCost << endl;
            return;
        }
        //만일 이미 이것보다 빠른 시간을 찾았다면, 이번에는 무시한다.
        if (dist[here][hereCost] < hereTimeCost)
            continue;
        for (auto next : adj[here]) {
            int there = get<0>(next);
            int thereCost = get<1>(next) + hereCost;
            int thereTimeCost = get<2>(next) + hereTimeCost;
            //만일 지원 금액을 초과하였다면, 이 경우는 무시한다.
            if (thereCost > M)
                continue;
            //더 짧은 시간을 찾았다면, 변경해주자.
            if (dist[there][thereCost] > thereTimeCost) {
                dist[there][thereCost] = thereTimeCost;
                pq.push({ -thereTimeCost, there, thereCost });
            }
        }
            
    }
 
    //여기까지 왔다는 것은 비용 내에 N번째 공항에 도착하지 못한 것이다.
    cout << "Poor KCM" << endl;
    return;
}
 
int main() {
    int T, N, M, K;
    int start, end, cost, timeCost;
    cin >> T;
    while (T--) {
        cin >> N >> M >> K;
        //초기화를 해준다.
        for (int i = 1; i <= N; i++) {
            adj[i].clear();
        }
        //티켓 정보 입력
        for (int i = 0; i < K; i++) {
            cin >> start >> end >> cost >> timeCost;
            adj[start].push_back({ end, cost, timeCost });
        }
 
 
        dijkstra(N, M);
    }
 
}

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!