이모저모

해결방법다이젝스트라를 이용하는 기본적인 문제이다.최단거리 방법을 이용하면서갱신될때 경로의 가짓수를 더하면 최종적인 가짓수를 구할 수 있다.시간 복잡도는 O((E+V)logV) 이다. 시간을 조금 더 줄이기 위해서원하는 노드에 도착하게 되었고, 그 때에 weight 보다 크면 루프를 탈출 한다.(단일 시발점에서 모든 정점을 다 구할 필요는 없다는 뜻이다.) 아래는 소스코드이다.#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000009#define INF 2147483647#defin..

해결방법단순 다이젝스트라를 사용하는 방법이다.문제 설명이 이해가 어렵게 만들어놔서 매우 틀렸다......단순 a,b 둘다 0개 도달되는 경우 -1그 이외의 경우에는 작은 값을 출력하면 된다. 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pair#define f first#define s se..

테두리에 도달하는 최솟값을 찾는 문제이다. 처음 DP를 생각하였으나 생각이 잘 나지 않아서 4방향으로 연결된 그래프 문제로 다이젝스트라를 이용하여 풀었다.(양의 정수 조건이 붙어 있으므로) 테두리에 도달하면 다이젝스트라의 성질에 의해서 그것이 가장 최솟값이므로 그 값을 출력한다. 아래는 소스 코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_..