[일반] 예전에 피갤에서 최장거리는 np라는걸 본거 같은데

[익명(220.76)]

아래글은 뭐 조건이 달려있어서 풀 수 있는건가?

[대학원오지마세요(publfl)]

level graph를 만들 수 있는 graph면 최장거리 구할 수 있을텐데

[카(211.57)]

나도 가중치 뒤집네 마네 하는 애들은 뭔소리하는건지 모르겠다 모든 간선이 음수라서 다익스트라 조건이랑 동치일때 빼고는 일반적인 그래프에서 최장거리 다항시간에 못구할텐데..? 밑에 글은 dag니까 걍 dp돌리면 되고

[익명(112.186)]

백준 임계경로 문제 보고 헷갈리는 사람들인 듯

[익명(61.39)]

dag면 걍 별다른 방법 없이 dp하면 선형에 됨

[EN_SA(encludingsalt)]

dag

[익명(210.105)]

simple path인 경우는 NP 맞는데 그 조건 없으면 그냥 음수 벨만포드야