글 읽기 - 10217 KCMTravel 질문입니다

mrcamel 9년 전 0

go(cur, prvi)가 호출되면

(cur로 올 수 있는 방법) x (cur에서 prvi로 갈 수 있는 방법)

을 리턴해주는 방식으로 만들었습니다.

예로 도착지가 4일 때

1->3, 1->2->3으로 오는 방법이 (4,3), (3,2)고 3->4 가 (1,2) 일때

1->4로 올 수 있는 방법은 (4 + 1, 3 + 2), (3 + 1, 2 + 2)입니다

직접 데이터도 몇개 만들어보고 몇시간 고민 해봤는데 잘 안풀립니다..

다른 분들은 소스 저보다 엄청 짧으신데 제가 괜히 복잡한 방향으로 생각한 것 같네요;

도움 주시면 정말 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
#define in cin
#define out cout
#define REPQ(i,s,e) for(int i=s; i<=e; i++)
#define MINN(a,b) ((a)<(b)?(a):(b))
 
#define MAX_N 100
 
int n, m, k;
struct ticketList
{
    vector<int> cost;
    vector<int> ttt;
 
    ticketList operator*(const ticketList t)
    {
        ticketList emptyList; //둘다 방법이 없을때
        if(t.cost.size() == 0 || this->cost.size() == 0) return emptyList;
 
        int D[10001]; for(int i=1; i<=m; i++) D[i] = 1e8;
 
        for(int i=0; i<cost.size(); i++)
        {
            for(int j=0; j<t.cost.size(); j++)
            {
                if(cost[i] + t.cost[j] > m) continue;
                else
                {
                    D[ cost[i] + t.cost[j] ] =
                        MINN(ttt[i] + t.ttt[j],
                        D[ cost[i] + t.cost[j] ]);
                }
            }
        }
        ticketList retr;
        for(int i=1; i<=m; i++)
        {
            if(D[i] != 1e8)
            {
                retr.cost.push_back(i);
                retr.ttt.push_back(D[i]);
            }
        }
 
        return retr;
    }
 
    ticketList operator+(ticketList t)
    {
        int D[10001]; for(int i=1; i<=m; i++) D[i] = 1e8;
 
        for(int i=0; i<cost.size(); i++)
        {
            if( cost[i] > m) continue;
            D[ cost[i] ] = MINN(ttt[i], D[ cost[i] ]);
        }
        for(int i=0; i<t.cost.size(); i++)
        {
            if( t.cost[i] > m) continue;
            D[ t.cost[i] ] = MINN(t.ttt[i], D[ t.cost[i] ]);
        }
 
        ticketList retr;
        for(int i=1; i<=m; i++)
        {
            if(D[i] != 1e8)
            {
                retr.cost.push_back(i);
                retr.ttt.push_back(D[i]);
            }
        }
 
        return retr;
    }
 
    void print()
    {
        for(int i=0; i<cost.size(); i++)
        {
            out << cost[i] << " " <<  ttt[i] << endl;
        } out << endl;
    }
};
 
ticketList lists[MAX_N+1][MAX_N+1]; // u -> v 로 갈 수 있는 리스트
ticketList pre[MAX_N+1]; //한번 계산한건 여기로 모아둠
int preb[MAX_N+1]; //pre가 있으면 1 아니면 0
int visit[MAX_N+1]; //방문 했으면 1 아니면 0
 
ticketList go(int cur, int prvi)
{
    if(cur == 1) //인천이면 
    {
        return lists[cur][prvi];
    }
    else
    {
        //이미 계산 되어 있으면
        if(preb[cur] == 1) return pre[cur]*lists[cur][prvi];
 
        ticketList retr; //지금 있는 곳과 연결된 곳을 탐색
        for(int i=1; i<=n; i++)
        {
            if(lists[i][cur].cost.size() != 0 && cur != i && visit[i] == 0)
            {
                visit[i] = 1;
                retr = retr + go(i, cur); //
                visit[i] = 0;
            }
        }
 
        preb[cur] = 1;
        pre[cur] = retr;
 
        //retr.print();
        //lists[cur][prvi].print();
 
        if(cur == prvi)
            return retr;
        else
            return retr*lists[cur][prvi]; //
    }
}
 
int main()
{
    int tc; in >> tc;
    while(tc--)
    {
        in >> n >> m >> k;
 
        //초기화
        REPQ(i,1,n)
        {
            REPQ(j,1,n)
            {
                lists[i][j].cost.erase(lists[i][j].cost.begin(), lists[i][j].cost.end());
                lists[i][j].ttt.erase(lists[i][j].ttt.begin(), lists[i][j].ttt.end());
            }
        }
        ticketList emptyList;
        REPQ(i,1,n) preb[i] = 0;
        REPQ(i,1,n) pre[i] = emptyList;
 
        REPQ(i,1,k)
        {
            int u, v, c, t; in >> u >> v >> c >> t;
            lists[u][v].cost.push_back(c);
            lists[u][v].ttt.push_back(t);
        }
 
        REPQ(i,1,n) visit[i] = 0;
 		//
        
        ticketList resList;
        resList = go(n, n);
 
        //가능한 것 중에 최소를 찾음
        int res = 1e8;
        for(int i=0; i<resList.cost.size(); i++)
        {
            if(resList.ttt[i] < res) res = resList.ttt[i];
        }
 
        /*
        for(int i=1; i<=n; i++)
        {
            out << i <<"(으)로 올 수 있는 방법" << endl;
            pre[i].print();
        }*/
 
        if(res != 1e8)
            out << res << endl;
        else
            out << "Poor KCM" << endl;
    }
    return 0;
}

h0ngjun7 9년 전 0

전 D(i, j) : i번째 도시를 방문할 때까지 j만큼의 비용을 사용했을 때, 가능한 최소 소요시간으로 table을 정의해서 O(E log E) 다익스트라와 동적계획법을 섞어서 풀었습니다.

mrcamel 9년 전 0

DP로 불필요한 부분을 어떻게 줄일 수 있을까요.

D(i, 9) = 1

D(i, 8) = 2

D(i, 7) = 3

D(i, 6) = 4 .. 이렇게 있으면 다 시도 해봐야 하지 않을까요?

답변 달아주셔서 감사합니다.

h0ngjun7 9년 전 1

다 시도해보더라도 O(N * M log K)의 시간복잡도를 가지므로 제가 짠 코드는 5036ms에 통과하더라구요.

아래는 제가 대회 당시에 작성했던 코드입니다. 참고하시길 바랍니다.

39번째 줄에 if (d[now.v][now.c] < now.d) continue; 를 넣지 않으니 8초 정도에 AC가 나오고

저 부분을 넣으니 5초 정도에 AC가 나오네요.

문제의 특성상 다익스트라를 돌다보면 D(i, j)가 한 번만 갱신되는 것이 아니라 여러 번 갱신되므로 저 부분이 있고 없고의 차이가 있습니다.

그리고 마지막으로 입력에서 주어지는 간선이 단방향임에 유의하시면 됩니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <memory.h>
#include <iostream>
using namespace std;
#define MN 105
#define MM 10005
string no = "Poor KCM";
struct data {
	int v, c, d;
	bool operator < (const data &d1) const {
		return d > d1.d;
	}
} dat, now, up;
int N, M, K, res;
vector <data> a[MN];
int d[MN][MM];
int main() {
	int runs;
	for (scanf("%d", &runs); runs--;) {
		scanf("%d%d%d", &N, &M, &K);
		for (int i = 1; i <= N; i++) a[i].clear();
		for (int i = 1; i <= K; i++) {
			int v1, v2, C, D;
			scanf("%d%d%d%d", &v1, &v2, &C, &D);
			dat.v = v2; dat.c = C; dat.d = D;
			a[v1].push_back(dat);
		}
		memset(d, -1, sizeof(d));
		res = 0;
		priority_queue <data> Q;
		dat.v = 1; dat.c = 0; dat.d = 0;
		Q.push(dat);
		d[1][0] = 0;
		while (!Q.empty()) {
			now = Q.top(); Q.pop();
			if (d[now.v][now.c] < now.d) continue;
			d[now.v][now.c] = now.d;
			for (int i = 0; i < a[now.v].size(); i++) {
				dat = a[now.v][i];
				if (dat.c + now.c > M) continue;
				if (d[dat.v][now.c + dat.c] == -1 || d[dat.v][now.c + dat.c] > now.d + dat.d) {
					d[dat.v][now.c + dat.c] = now.d + dat.d;
					up.v = dat.v;
					up.c = now.c + dat.c;
					up.d = now.d + dat.d;
					Q.push(up);
				}
			}
		}
		res = 2147483647;
		for (int i = 0; i <= M; i++) if (d[N][i] != -1 && res > d[N][i]) res = d[N][i];
		if (res != 2147483647) printf("%d\n", res);
		else cout << no << "\n";
	}
}

mrcamel 9년 전 0

다시 답변주셔서 감사합니다.

답변 달아주신 코드보고 참고해서 다시 짜봤는데 잘 안굴러가네요.. 내일 다시 생각해보겠습니다.

즐거운 연말되세요!

amugeona 9년 전 1

이 문제가 매우 짧게 돌아가던 분들은 비용처리를 그리디로 했더니 됐다는 얘기가 있었던거 같네요. 모든 비용에 대해 DP로 처리하지 않고도...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10217 KCMTravel 질문입니다

mrcamel 9년 전 0

h0ngjun7 9년 전 0

mrcamel 9년 전 0

h0ngjun7 9년 전 1

mrcamel 9년 전 0

amugeona 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말