250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 백준#boj#16932#모양만들기
- 백준#BOJ#8012#한동이는영업사원
- 백준#BOJ#14501#퇴사#브루트포스
- 백준#BOJ#1939#중량제한
- 백준#BOJ#2615#오목
- 백준#boj#12755
- 백준#BOJ#12865#평범한배낭
Archives
- Today
- Total
순간을 성실히, 화려함보단 꾸준함을
[ boj : 2982 ]국왕의 방문 본문
문제 : 국왕이 방문하는데 이때 교차로 사이의 도로는 국왕이 먼저 건너면 건널 수 없습니다.
이때 상그니가 목적지까지 최소시간으로 갈 수 있는 시간을 구하시오
해설 : 아우 전 문제를 잘못 읽어서 엄청 고생했었습니다. 교차로에는 공유 가능하나 교차로 사이의 도로가 겹치면 안되는 것 입니다. 이때도, 상그니가 먼저 교차로에는 들어갈 수 있습니다.
무조건 국왕이 먼저 도로를 건너면 건너지 못합니다.
다익스트라 알고리즘을 사용해서 구하면 되는데 국왕이 지나가는 도로를 처리를 해주어야겠죠.
먼저 국왕이 지나는 도로를 언제부터 언제까지 건널 수 없는지 범위로 전처리로 해주고 나서 다익스트라를 돌려 하나씩 구분지어 가며 답을 도출해 나아가면 됩니다.
만약 국왕이 지나고 있어 지나갈 수 없는 상태라면 국왕이 도로를 다 지나갈때동안 기다리고 나서 건너면 되죠.
#include<bits/stdc++.h>
using namespace std;
struct a {
int s, e;
}A[1001][1001];
struct info {
int to, weight;
bool operator<(const info& cur) const {
return weight > cur.weight;
}
};
int n, m;
int a, b, k, g;
int arr[1000],dist[1001];
int cp[1001][1001];
vector<info> v[1001];
const int INF = (int)1e9;
int dijk();
int main()
{
int x, y, z;
cin >> n >> m >> a >> b >> k >> g;
for (int i = 0; i < g; i++)cin >> arr[i];
for (int i = 0; i < m; i++) {
cin >> x >> y >> z;
v[x].push_back({ y,z });
v[y].push_back({ x,z });
cp[x][y] = cp[y][x] = z;
}
int prefix = 0;
for (int i = 1; i < g; i++) {
int p = arr[i - 1];
int q = arr[i];
A[p][q].s =A[q][p].s= prefix;
prefix += cp[p][q];
A[p][q].e = A[q][p].e = prefix;
}
cout<<dijk()-k;
return 0;
}
int dijk()
{
for (int i = 1; i <= n; i++)dist[i] = INF;
priority_queue<info> pq;
dist[a] = k;
pq.push({ a,k });
while (!pq.empty())
{
info cur = pq.top();
pq.pop();
if (dist[cur.to] < cur.weight)continue;
for (int i = 0; i < v[cur.to].size(); i++) {
int next = v[cur.to][i].to;
int next_weight = v[cur.to][i].weight;
if (dist[next] > dist[cur.to] + next_weight) {
if (A[cur.to][next].s <= dist[cur.to] && dist[cur.to] < A[cur.to][next].e) {
dist[next] = A[cur.to][next].e + next_weight;
}
else
dist[next] = dist[cur.to] + next_weight;
pq.push({ next,dist[next] });
}
}
}
return dist[b];
}
추가로 저가 항상 찝찝했던 부분이 정점간의 간선을 표현할때 필요가 없는 부분을 어쩔 수 없이 감안하고 배열을 써야된다는게 싫었는데(메모리때문에) 이를 해결해 줄 수 있는 기가막힌 방법을 봤네요....
앞으로 이렇게 이용하시면 될 것 같습니다.
*djm03718님의 코드입니다.(감사합니다)
#include <bits/stdc++.h>
using namespace std;
struct A {
int i, w;
bool operator<(const A &o) const {
return w > o.w;
}
};
map<int, int> adj[1005], mp[1005];
int seq[1005];
int d[1005];
const int inf = (int)1e9;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, a, b, k, g, i;
cin >> n >> m >> a >> b >> k >> g;
for (i = 0; i < g; i++)
cin >> seq[i];
for (i = 0; i < m; i++)
{
int u, v, l;
cin >> u >> v >> l;
adj[u][v] = adj[v][u] = l;
}
int cur = 0, t = 0;
for (i = 0; i < g; i++)
{
int x = seq[i];
if (i != 0)
{
mp[cur][x] = mp[x][cur] = t;
t += adj[cur][x];
}
cur = x;
}
for (i = 1; i <= n; i++)
d[i] = inf;
d[a] = k;
priority_queue<A> pq;
pq.push({ a, k });
while (pq.size())
{
A cur = pq.top();
pq.pop();
if (d[cur.i] != cur.w)
continue;
for (auto x : adj[cur.i])
{
int w = cur.w;
auto it = mp[cur.i].find(x.first);
if (it != mp[cur.i].end() && it->second <= cur.w)
w = max(w, it->second + x.second);
w += x.second;
if (w < d[x.first])
{
d[x.first] = w;
pq.push({ x.first, d[x.first] });
}
}
}
cout << d[b] - k;
}
'알고리즘,SQL > 백준,BOJ' 카테고리의 다른 글
[ boj : 1976] 여행 가자 (0) | 2021.01.28 |
---|---|
[ boj : 14395 ] 4연산 (0) | 2021.01.28 |
[ boj : 1503 ] 세 수 고르기 (0) | 2021.01.27 |
[ boj : 17208] 카우버거 알바생 (0) | 2021.01.25 |
[ boj : 14225 ]부분수열의 합 (0) | 2021.01.23 |