백준 9370번 : 미확인 도착지 / C++
2023. 3. 21. 20:31ㆍ개인공부/코딩테스트
https://www.acmicpc.net/problem/9370
9370번: 미확인 도착지
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서
www.acmicpc.net
내가 푼 문제들중에 가장 어려운 문제였다. 문제의 길이와 변수들도 많이 있어서 복잡한 문제였다. 76번줄에 들어왔을때에더 map에도 추가를 했어야했는데 안해줘서 틀렸고 그 이후에는 잘 해결하였다. 핵심은 Info 비교 연산과정에서 g,h를 지나면 true 인 경우에 먼저 map에서 나오게 만들었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct Info
{
int cost;
bool pass;
Info()
:cost(0)
, pass(false)
{}
Info(int cost, bool pass)
:cost(cost), pass(pass) {}
bool operator <(const Info& other)const {
if (cost < other.cost)
return true;
else if (cost == other.cost && pass > other.pass)
return true;
return false;
}
};
int n, m, t; // 교차로, 도로, 목적지 후보
int s, g, h; // 예술가들 출발지, g와 h 사이에 있는 도로를 지나감
vector<pair<int,int>> Edge[2001]; // first 간선 second value
vector<int> TargetList;
Info CostInfo[2001]{};
bool Visited[2001]{};
multimap<Info, int> M;
void dijkstra(int num)
{
M.insert(make_pair(Info(0, false), num));
while (!M.empty())
{
auto iter = M.begin();
Info ParentInfo = iter->first;
int ParentIndex = iter->second;
if (Visited[ParentIndex] == true)
{
M.erase(iter);
continue;
}
Visited[ParentIndex] = true;
//방문한 경우
for (int i = 0; i < Edge[ParentIndex].size(); ++i)
{
int ChildIndex = Edge[ParentIndex][i].first;
int ChildCost = Edge[ParentIndex][i].second;
if (CostInfo[ChildIndex].cost == 0)
{
CostInfo[ChildIndex].cost = ParentInfo.cost + ChildCost;
if (ParentInfo.pass == true || (ParentIndex == g && ChildIndex == h) || (ParentIndex == h && ChildIndex == g))
CostInfo[ChildIndex].pass = true;
else
CostInfo[ChildIndex].pass = false;
M.insert(make_pair(CostInfo[ChildIndex], ChildIndex));
}
else if (CostInfo[ChildIndex].cost > ParentInfo.cost + ChildCost)
{
CostInfo[ChildIndex].cost = ParentInfo.cost + ChildCost;
if (ParentInfo.pass == true || (ParentIndex == g && ChildIndex == h) || (ParentIndex == h && ChildIndex == g))
CostInfo[ChildIndex].pass = true;
else
CostInfo[ChildIndex].pass = false;
M.insert(make_pair(CostInfo[ChildIndex], ChildIndex));
}
else if (CostInfo[ChildIndex].pass == false && CostInfo[ChildIndex].cost == ParentInfo.cost + ChildCost)
{
if (ParentInfo.pass == true || (ParentIndex == g && ChildIndex == h) || (ParentIndex == h && ChildIndex == g))
CostInfo[ChildIndex].pass = true;
M.insert(make_pair(CostInfo[ChildIndex], ChildIndex));
}
}
M.erase(iter);
}
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int TestCase;
cin >> TestCase;
for (int i = 0; i < TestCase; ++i)
{
// 초기화
for (int j = 0; j <= 2000; ++j)
{
Edge[j].clear();
CostInfo[j].cost = 0;
CostInfo[j].pass = false;
Visited[j] = false;
}
TargetList.clear();{};
// 대입
cin >> n >> m >> t >> s >> g >> h;
for (int j = 0; j < m; ++j)
{
int a, b, d; // a와 b 사이의 길이 d의 양방향 도로
cin >> a >> b >> d;
Edge[a].push_back(make_pair(b, d));
Edge[b].push_back(make_pair(a, d));
}
for (int j = 0; j < t; ++j)
{
int target;
cin >> target;
TargetList.push_back(target);
}
dijkstra(s);
set<int> s;
for (int i = 0; i < TargetList.size(); ++i)
{
int number = TargetList[i];
if (CostInfo[number].pass == true && CostInfo[number].cost != 0)
s.insert(number);
}
for (auto iter = s.begin(); iter != s.end(); ++iter)
cout << *iter << ' ';
cout << '\n';
}
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 2589번 : 보물섬 / C++ (0) | 2023.03.23 |
|---|---|
| 백준 11657번 : 타임머신 / C++ (0) | 2023.03.22 |
| 백준 1504번 : 특정한 최단 경로 / C++ (0) | 2023.03.20 |
| 백준 1753번 : 최단 경로 / C++ (0) | 2023.03.18 |
| 백준 1707번: 이분 그래프 / C++ (0) | 2023.03.16 |