글 읽기 - dp로 풀었는데 9%에서 틀리네요...ㅠㅠ 제가 놓친부분이 있을까요?

worldbright 4년 전 0

플로이드 와샬 알고리즘을 안보고 dp로 풀어봣는데

봐도 알고리즘 자체는 거의 비슷한 것 같은데,, 9%에서 틀렸다고 나오네요 ㅠㅠㅠㅠ

제가 실수한 부분이 있을까요?

//
//  main.cpp
//  백준 2660 회장뽑기
//
//  Created by 최세현 on 2019/11/19.
//  Copyright © 2019 최세현. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#define INF 2147483647
using namespace std;
vector<vector<int>> minimumPath(51, vector<int>(51, INF));
vector<int> directPath[51];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> res;
int resScore;
vector<int> resVector;
int visited[51] = {0};

int findPath(int a, int b)
{
    int &ret = minimumPath[a][b];
    if(ret != INF)
        return ret;
    visited[a] = 1;
    for(auto i : directPath[a])
    {
        if(!visited[i])
            minimumPath[b][a] = ret = min(ret, minimumPath[a][i] + findPath(i,b));
    }
    visited[a] = 0;
    return ret;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int n, input1 = 0, input2 = 0;
    cin >> n;
    while((cin >> input1 >> input2) && (input1 != -1 || input2 != -1))
    {
        minimumPath[input1][input2] = 1;
        minimumPath[input2][input1] = 1;
        directPath[input1].push_back(input2);
        directPath[input2].push_back(input1);
    }
    for(int i = 1, maxPath = 0; i <= n; i++, maxPath = 0)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i==j)
                minimumPath[i][j] = 0;
            else if(minimumPath[i][j] == INF)
                findPath(i, j);
            maxPath = max(maxPath, minimumPath[i][j]);
        }
        res.push(make_pair(maxPath, i));
    }
    resScore = res.top().first;
    while(!res.empty() && res.top().first == resScore)
    {
        resVector.push_back(res.top().second);
        res.pop();
    }
    
    cout << resScore << " " << resVector.size() << endl;
    for(auto i : resVector)
        cout << i << " ";
    cout << endl;
    return 0;
}

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

문제

문제

출처

ICPC

dp로 풀었는데 9%에서 틀리네요...ㅠㅠ 제가 놓친부분이 있을까요?

worldbright 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말