Pony Express (Small,Large) C++ - 백준 14807,14808

https://www.acmicpc.net/problem/14807
https://www.acmicpc.net/problem/14808

최단경로 문제.

처음 볼때에는 간단한 BFS 문제인줄 알았으나

사실 최단경로 알고리즘으로 푸는 문제.

문제 접근

$U_k$에서 $V_k$로 가는 경로는 항상 존재한다.

따라서 $U_k \rightarrow V_k$ 거리도 항상 존재한다.

먼저 거리를 구해주면 소요시간도 구할 수 있다.

이를 구하는 과정은 다음과 같이 생각해볼 수 있다.

• 플로이드로 모든 정점 $V_i \rightarrow V_j$ 최단경로를 구한다.
• 플로이드로 최소 소요시간을 구하는데 이때 $DP[i][j]$가 말의 거리 제한보다
  크면 $INF$값을 넣어 불가능한 경우를 표현해준다.
• 불가능한 경우를 표현해줌에도 플로이드로 거쳐가는 경로 $k$ for문이 작동하므로 가능한 경로에 대해 최소 소요시간은 보장된다.
• 최소 소요시간은 거리를 각 도시 $i$말에 대해 $S[i]$로 나누어 준 값이다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define INF (ll)2e11
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout.precision(7);
    cout << fixed;
    int t;
    cin >> t;
    for(int p=1;p<=t;p++){
        int n,q;
        cin >> n >> q;
        vector<double> E(n),S(n);
        vector<vector<double>> dp(n,vector<double> (n));
        vector<vector<ll>>  d(n,vector<ll> (n));
        for(int i=0;i<n;i++) cin >> E[i] >> S[i];
        for(int i=0;i<n;i++) for(int j=0;j<n;j++){
            cin >> d[i][j];
            if(d[i][j]==-1) d[i][j]=INF;
        }
        for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++){
            if(E[i]<d[i][j]) dp[i][j]=INF;
            else dp[i][j]=d[i][j]/S[i];
        }
        for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        cout << "Case #" << p << ": ";
        for(int i=0;i<q;i++){
            int u,v;
            cin >> u >> v;
            cout << dp[u-1][v-1] << ' ';
        }
        cout << '\n';
    }
    return 0;
}