Codeforces Round #119 (Div. 1) B. AlgoRace

그래프 + dp 이다.

N<=60, M<=60, R<=10^5, K<=1000

N개의 노드가 있고 M개의 차가 있고 R개의 쿼리가 들어온다.

각 M개의 차마다 인접행렬이 주어지는데 i,j 의 원소는 이 차를 탔을때 i번노드에서 j번 노드로 가는 데 걸리는 시간이다.

각각의 쿼리는 출발지 S, 도착지 E, 차를 갈아탈 수 있는 최대 횟수 K 로 이루어진다.

각각의 쿼리에 대해 S에서 E로 최대 K번 차를 갈아탈 수 있을 때의 최단 시간을 답하면 된다.

다익스트라 응용문제에서 처럼 현재 위치와 갈아탄 횟수와 현재 타고있는 차에 따라 노드를 더 세분화 하여 그래프를 만들어서 풀려고 했더니 노드의 수만 N*M*K, 즉 최악의 경우 360만개가 될 수 있다는 말이며, 엣지는 꽉 찬 그래프 이기때문에 엄청나게 많다..

다익스트라로는 못 구할 것같고 점화식을 세워보다가 시간내에 돌아갈 만한 점화식이 잘 안세워 져서 결국 답을 봤다.

dp[m][i][j] : i에서 j까지 m번 차를 갈아타고 가는 최소 시간

dp[m][i][j] = (for k 0 to N-1) min(dp[m-1][i][k] + dp[0][k][j])

dp[0][i][j] 는 하나의 차만 타고 i에서 j로 가는 최단 시간이기 때문에

각 M개의 차에 대해 플로이드를 돌려서 i~j 의 최단 시간을 모든 차 중에 최소값을 취하면된다.

여기까지 시간 복잡도는 dp[0][i][j]를 구하는 데에 O(M*N^3), 그리고 dp[m][i][j] 를 구하는 데에 O(K*N^3) 이다.(최대 K번 갈아 탈 수 있기 때문)

하지만 M*N^3은 그렇다 쳐도 K*N^3 는 좀 오래걸린다. 2억정도됨..

근데 조금만 더 생각해보면 출발지에서 도착지까지 가는 경로상에 포함된 노드는 최대 N개 이다. 이미 지났던 노드를 한번더 방문한다면 최단 경로 일 수가 없기 때문이다. 간단히 말해서 우리가 구하는 최단경로는 무조건 단순 경로이기 때문에 같은 노드를 두번이상 지나지 않고 그렇기 때문에 가는동안 아무리 차를 많이 갈아타도 N-1번 갈아타게 된다. 왜냐하면 차는 노드에서 갈아타는거고 지나는 노드는 출발지를 제외하고 N-1개 이기 때문이다. 그렇기때문에 입력으로 주어진 K가 60보다 크고 1000보다 작거나 같은 수일 때 K를 60으로 바꿔도 상관이 없다.

그래서 O(K*N^3) -> O(N^4). 즉 최종 복잡도는 O(M*N^3+N^4)

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int N,M,R,S,E,K;
int dist[63][63][63];
int dp[1003][63][63];
int main() {
    memset(dp,0x3c,sizeof(dp));
    inp3(N,M,R);
    FOR(m,M){
        FOR(i,N){
            FOR(j,N){
                scanf("%d",&dist[m][i][j]);
            }
        }
    }
 
    FOR(m,M){
        FOR(k,N){
            FOR(i,N){
                FOR(j,N){
                    dist[m][i][j] = min(dist[m][i][j], dist[m][i][k] + dist[m][k][j]);
                }
            }
        }
    }
    FOR(m,M) FOR(i,N) FOR(j,N) dp[0][i][j] = min(dp[0][i][j], dist[m][i][j]);
 
    REP(l,1,N){
        FOR(k,N){
            FOR(i,N){
                FOR(j,N){
                    dp[l][i][j] = min(dp[l][i][j],dp[l-1][i][k] + dp[0][k][j]);
                }
            }
        }
    }
 
    FOR(i,R){
        inp3(S,E,K);
        printf("%d\n",dp[min(K,N)][S-1][E-1]);
    }
    return 0;
}