yulee

🤔문제 이해 말은 거창하지만 전형적인 다익스트라 문제에 방문할 수 없는 구간이 존재한다는 것만 추가된 문제이다. 🔥풀이🔥 다익스트라로 구현을 하고 상대의 시야에 보이는 분기점은 방문하지 않도록 해주기만 하면 된다. 넥서스의 경우는 시야가 보이지만 갈 수 있어야 하므로 따로 0으로 처리해주었다. #include #include #include using namespace std; #define INF 10000000000 int n, m, a, b, t; bool sight[100001]; vector edge(100001); long long dist[100001]; int main() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false)..

🤔문제 이해 최단거리로 도달할 수 있는 도시들 중 최단거리가 k인 경우만 출력해주는 문제이다. 💡첫번째 아이디어 다익스트라 문제인데 그냥 다익스트라를 수행한 후 최단 거리가 k인 값만 출력해주면 된다고 생각했다. 🔥풀이🔥 다익스트라 수행 후 dist[i]값이 k인 i만 출력 ❌트러블 슈팅 dist를 모두 INF를 바꿔주고 시작점인 x만 0으로 바꿔주는 코드가 없어서 첫 제출에서 틀렸다. dist[x] =0 코드 추가 후 제대로 돌아갔다. #include #include #include using namespace std; #define INF 987654321 int n, m, k, x; vector edge; int dist[300002]; int main() { cin.tie(nullptr); cou..

🤔문제 이해 1번 정점에서 N번 정점까지 가는 모든 경로 중에 최대 k개의 도로 이동 시간이 0이 되었을 때 시간이 가장 적게 드는 경로의 시간을 구하는 문제이다. 💡첫번째 아이디어 다익스트라 문제이지만 도로를 포장해야 한다는 점에서 더 어려웠다. 스터디 멘토님이 가르쳐준 방법은 아래 풀이와 같다. 🔥풀이🔥 최단경로 문제에서 최단거리를 저장하는 1차원 배열을 2차원 배열로 바꾸어 dist[i][j]에서 j는 도로를 포장한 횟수를 의미한다. 따라서 다익스트라로 구현하되 j값이 문제에서 주어지는 포장가능한 도로의 개수 k보다 작을 때 도로를 한 번 포장한 값을 j+1에 넣어주고 포장하지 않았을 때의 값을 j에 업데이트 해준다. 정점 n에 도착하면 break해주고 나서는 도로를 몇번 포장했을 때 가장 최소인지..

🤔문제 이해 시작점에서 각 정점을 방문하기 위해 필요한 최소 비용을 구하는 문제이다. 💡첫번째 아이디어 문제가 그냥 딱 다익스트라 문제라 다익스트라를 이용했다. 🔥풀이🔥 다익스트라를 그대로 구현하였고, 다음 정점까지의 거리를 우선순위큐에 넣어주기 전에 이미 그 정점까지 최소거리보다 크면 큐에 넣어주지 않고 continue를 해주었다. 그리고 우선순위큐에 들어있는 정점이 이미 최소거리가 확정되었다면 그 때에도 continue를 해줘서 불필요한 연산을 줄여주었다. 아래는 제출한 코드이다. #include #include using namespace std; #define INF 100000000 int dist[20002], v, e, k; int main() { cin.tie(nullptr); cout.t..