BOJ 10217 KCM Travel(Python 3)

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

총 24번 제출을 하였다...

(통과하기전)

(C언어로 통과했을 때)

(파이썬으로 통과했을 때)

파이썬으로 다익스트라+DP를 구현하는데 자꾸 시간 초과,메모리 초과,틀렸습니다가 떴다.

from heapq import *
input=__import__('sys').stdin.readline
for __ in range(int(input())):
    n,m,k=map(int,input().split())
    D=[[] for _ in range(n+1)]
    for i in range(k):
        u,v,c,d=map(int,input().split())
        D[u].append((v,c,d))
    S=[[float('INF')]*(m+1) for _ in range(n+1)]
    S[1][0]=0
    q=[]
    heappush(q,[0,0,1])
    while q:
        t,e,x=heappop(q)
        if S[x][e]!=t:continue
        for nx,ne,nt in D[x]:
            if ne+e<=m:
                if S[nx][ne+e]>nt+t:
                    S[nx][ne+e]=nt+t
                    heappush(q,[nt+t,ne+e,nx])
    k=min(S[n])
    print([k,'Poor KCM'][k==float('INF')])

처음에는 내가 시간 줄일 수 있는 곳을 못 찾아서 그런 줄 알고, 열심히 찾아보았으나, 다음날까지 도저히 안보여서 C언어로 다익스트라+DP를 구현하여 통과하였다.

파이썬은 다익스트라+DP로 풀지 못하는 문제이다.(시간 초과)

그래서 DP로 풀어야한다.

C언어는 큐와 튜플을 어떻게 구현하는지 몰라 https://blog.encrypted.gg/164 이 글을 참고해서 만들었다.

C언어 코드 확인

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>
#include <functional>
#define INF 987654321
using namespace std;
typedef tuple<int,int,int> Tuple;
int D[102][10002];
int main(void){
    int T;
    cin >> T;
    while (T--){
        int n,m,k,u,v,c,d;
        cin >> n >> m >> k;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                D[i][j]=INF;
        D[1][0]=0;
        vector<Tuple> pp[102];
        while (k--){
            cin >> u >> v >> c >> d;
            pp[u].push_back({v,c,d});
        }
        priority_queue<Tuple,vector<Tuple>,greater<Tuple>> q;
        q.push({ 0,0,1 });
        int ans=INF;
        while(!q.empty()){
            auto cur=q.top();
            q.pop();
            int t=get<0>(cur);
            int e=get<1>(cur);
            int x=get<2>(cur);
            if (D[x][e]!=t) continue;
            if (x==n){
                ans=t;
                break;
            }
            for (auto near : pp[x]){
                int nx = get<0>(near);
                int ne = get<1>(near);
                int nt = get<2>(near);
                if (e+ne>m) continue;
                if (D[nx][e+ne] > t+nt){
                    D[nx][e+ne]=t+nt;
                    q.push({nt+t,e+ne,nx});
                }
            }
        }
        if (ans==INF)
            cout << "Poor KCM" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}
 

파이썬 코드 확인

input=__import__('sys').stdin.readline
Max=float('INF')
for __ in range(int(input())):
    n,m,k=map(int,input().split())
    D=[[] for _ in range(n+1)]
    for i in range(k):
        u,v,c,d=map(int,input().split())
        D[u].append((v,c,d))
    S=[[Max]*(m+1) for _ in range(n+1)]
    S[1][0]=0
    for e in range(m+1):
        for x in range(1,n+1):
            if S[x][e]==Max:continue
            t=S[x][e]
            for nx,ne,nt in D[x]:
                if ne+e>m:continue
                S[nx][ne+e]=min(S[nx][ne+e],t+nt)
    k=min(S[n])
    print([k,'Poor KCM'][k==Max])