많이 헤맸던 문제이다.
1. BFS(Priority queue)
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 1111111111
int N, M, S, E;
vector<pair<int, int>> vec[10001];
int visit[10001];
int bfs(){
priority_queue<pair<int, int> > q;
q.push({ INF, S });
while (!q.empty()){
int cost = q.top().first;
int curr = q.top().second;
q.pop();
if (curr == E)
return cost;
if (visit[curr]) continue;
visit[curr] = 1;
for (auto i : vec[curr]){
int next = i.first;
int ncost = min(cost,i.second);
if (visit[next]) continue;
q.push({ ncost, next});
}
}
return 0; //도달이 안된 경우(불가능)
}
int main(){
scanf("%d%d", &N, &M);
for (int m = 0; m < M; m++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
vec[a].push_back({ b, c });
vec[b].push_back({ a, c });
}
scanf("%d%d", &S, &E);
printf("%d\n",bfs());
return 0;
}
| cs |
2. Binary Search - BFS
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 1111111111
int N, M, S, E;
vector<pair<int, int>> vec[10001];
int minim = 1, maxim = 0, middle;
int visit[10001];
bool bfs(int x){
queue<pair<int, int> > q;
q.push({ INF, S });
while (!q.empty()){
int cost = q.front().first;
int curr = q.front().second;
q.pop();
if (curr == E)
return true;
if (visit[curr]) continue;
visit[curr] = 1;
for (auto i : vec[curr]){
int next = i.first;
int ncost = min(cost,i.second);
if (visit[next] || x > ncost) continue;
q.push({ ncost, next});
}
}
return false; //도달이 안된 경우(불가능)
}
int main(){
scanf("%d%d", &N, &M);
for (int m = 0; m < M; m++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
vec[a].push_back({ b, c });
vec[b].push_back({ a, c });
maxim = maxim < c ? c : maxim;
}
scanf("%d%d", &S, &E);
while (minim <= maxim){
middle = (minim + maxim) / 2;
if (bfs(middle))
minim = middle + 1;
else
maxim = middle - 1;
for (int n = 1; n <= N; n++)
visit[n] = 0;
}
printf("%d\n", maxim);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기