w에 -1을 곱해 최단 경로를 구하는 문제로 바꾼다.벨만포드로 그래프를 순회하고 사이클이 있는 지 확인한다.출발지에서 사이클로 갈 수 있고, 사이클에서 도착지로 갈 수 있다면 무한루프가 발생해 답은 -1이 된다.벨만포드로 출발지에서 사이클로 갈 수 있는 지 알 수 있고,역방향 BFS로 사이클에서 도착지로 갈 수 있는 지를 알 수 있다.무한루프가 발생하지 않는다면 경로복원으로 경로를 찾아 출력한다. #include #define ll long long#define X first#define Y second#define fastio ios::sync_with_stdio(0), cin.tie(0);using namespace std;vector > > edges;vector > back_edges;int vi..
https://www.acmicpc.net/problem/2104 https://www.acmicpc.net/problem/6549 2104 부분배열 고르기구간의 최솟값*구간합을 최대로 만들어야 한다.A[i]를 전체 구간의 최솟값이라고 했을 때, A[i]를 포함하여 최대값을 만들려면 A[i]*전체구간합이 최대값인 것은 자명하다.다른 최대값을 확인하려면 A[i]을 제외한 다른 구간을 봐야만 한다.(~A[i-1]) , (A[i+1]~) 이 두 구간으로 자를 수 있다.이를 반복하면 최대값을 얻을 수 있다. #include #define ll long long#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;l..