Approach 최단 경로의 길이를 물어보는 것에서 다익스트라 문제임을 쉽게 파악할 수 있다. 이 문제에서 눈여겨 봐야할 지점은 반드시 거쳐야하는 정점이 있다는 것이다. 잠시 기억을 더듬어서 고등학교 경우의 수 문제에서 최단거리를 구할 때, 특정한 지점을 반드시 지나는 문제를 어떻게 풀었는지를 잘 생각해보자. 아마도 특정한 지점을 기준으로 분할해서 풀었던 기억이 있을 것이다. 마찬가지로 위 문제도 특정한 지점을 기준으로 분할해서 풀어주면 된다. 두 정점을 순서대로 v1, v2라고 하고, d(a, b)를 a부터 b까지 가는데 필요한 최단 경로의 길이라고 정의하자 d(1, N) = min(d(1, v1) + d(v1, v2) + d(v2, N), d(1, v2) + d(v2, v1) + d(v1, N))이다..

Approach 전형적인 다익스트라 문제 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef long long ll; typedef vector ullv1; typedef vector ullv2; const int INF = 987654321; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].push_back({b - 1..

Approach 대표적인 다익스트라 문제이다. w가 양수인 최단 경로를 구하는 상황이므로 다익스트라로 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; const int INF = 987654321; int v, e; vector dist; vector edge; bool visited[20000]; int main(void) { fastio; memset(visited, 0, sizeof(visited)); cin >> v >> e; edge = vector(v); dist = vector(v); fill(dist.beg..