문제: http://www.codeforces.com/contest/189/problem/D

이하 문제 및 제 풀이 엉엉

문제: 레이싱을 하는데 차(m<=60)가 여러 대 있고 도시(n<=60)들은 다 방향성 완전그래프로 연결되어 있어요. 단 차별로 그래프 코스트가 모두 다르구요.
그래프에 대한 정보가 모두 들어오고 r<=100,000 개 레이싱 쿼리가 들어와요. 쿼리는 시작점, 도착점, 레이싱 도중 차를 갈아탈 수 있는 숫자<=1,000 으로 구성되어 있습니다.

각 쿼리별 최단거리를 구하는 문제에요.

풀이: 차별 코스트 그래프에 대해서 플로이드로 각 차별 도시간 최단거리를 모두 구해둡니다. 그 뒤 DP(현재도시, 목표도시, 갈아탈 수 있는 수)를 정의해서 위에서 플로이드로 구한 코스트테이블을 통해 매 DP간 참조마다 차를 한 번씩 강제로 갈아탄다고 가정했습니다.

근데 현실은 WA...ㅜㅜ

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
long long graph[60][60][60];
int n, m, r;
long long dp[60][60][60];
 
long long getAns(int cur, int tar, int left)
{
    if(left>59) return getAns(cur, tar, 59);
    long long &ret=dp[cur][tar][left];
    if(ret!=-1) return ret;
 
    ret = 99999999;
    if(left == 1) for(int i=0;i<m;i++) ret=min(ret, graph[i][cur][tar]);
    else if (left > 1) for(int i=0;i<n;i++) ret = min(ret, getAns(cur, i, 1) + getAns(i, tar, left-1));
 
    return ret;
}
 
int main(void)
{
    scanf("%d %d %d", &n, &m, &r);
    for(int q=0;q<m;q++)
    {    
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%I64d", graph[q][i]+j);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) if(graph[q][i][k]+graph[q][k][j]<graph[q][i][j]) graph[q][i][j] = graph[q][i][k]+graph[q][k][j];
    }
 
    memset(dp, -1, sizeof(dp));
    for(int i=0;i<r;i++)
    {
        int s, t, K;
        scanf("%d %d %d", &s, &t, &K);
        printf("%I64d\n", getAns(s-1, t-1, K+1));
    }
        
    return 0;
}