다익스트라4 [BOJ] 백준 9370번: 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지�� www.acmicpc.net 시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때, 시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다. 먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SL.. 2020. 8. 9. [BOJ] 백준 14938번: 서강그라운드 모든 지점에서 다익스트라를 반복하여 최대값을 찾는 문제 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[101]; int dist[101]; int item[101]; int n, m, r; bool visit[101] = { 0, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> r; for (int i = 1; i > item[i]; } for (int i = 0; i < r; i++) { .. 2020. 6. 19. [BOJ] 백준 11779번: 최소비용 구하기 2 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[1001]; int dist[1001]; int pre[1001]; int n, m; int s, e; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; memset(pre, -1, sizeof(pre)); for (int i = 1; i > a >> b >> c; v[a].push_back({ b,c }); } cin >> s >> e; priority_.. 2020. 6. 19. [BOJ] 백준 1238번: 파티 주어진 입력을 정방향, 역방향 2개의 벡터로 저장하여 파티가 열리는 노드를 시작으로 다익스트라를 2번 수행하여 오고 가는데 걸린 최단 경로 합의 최대를 출력하는 문제 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[10001]; vector v2[10001]; int dist[10001]; int dist2[10001]; int n, m, x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> x; for (int .. 2020. 6. 19. 이전 1 다음
