글 읽기 - 데이터를 추가해주세요

adxx 2년 전 0

N이 800으로 O(N^3)풀이는 TLE를 받아야합니다

하지만 N^3풀이가 AC를 받습니다

제출 번호: 30168973

통과하는 풀이는 아래와 같습니다

요약: 다익스트라를 2번 쓰는 풀이가 정해같은데, 플로이드로 풀립니다

#include "iostream"
#include "algorithm"

using namespace std;
int dp[900][900];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, e;
    cin >> n >> e;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j) dp[i][j]=900000;
    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dp[u][v] = w;
        dp[v][u] = w;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                if (j==k) continue;
                dp[j][k] = min(dp[j][k], dp[j][i]+dp[i][k]);
            }
    int u, v;
    cin >> u >> v;
    int ans = min(dp[1][u]+dp[u][v]+dp[v][n], dp[1][v]+dp[v][u]+dp[u][n]);
    if (ans>=900000) cout << "-1" << "\n";
    else cout << ans << "\n";
    return(0);
}

startlink 2년 전 0

데이터 첨부해주세요.

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

문제

문제

출처

ICPC

데이터를 추가해주세요

adxx 2년 전 0

startlink 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말