11781 퇴근 시간 https://www.acmicpc.net/problem/11781
1. 도시들
그래프가 주어진다.
도시들 중에는 '중요도시'가 K개 존재하는데 모든 중요도시들이 연결될 수 있는 최소비용을 구하는 문제이다.
일단 문제를 보고 2938 3인통화 풀듯이
$\min_{i=1}^{N}$($\sum_{j=1}^{K}dist[j][i]$)를 구하는 방식으로 풀면 될것같았다.
($dist[j][i]$ : $important[j]$에서 $i$로 가는 최소 비용)
1부터 N사이에 있는 정점 $i$로부터 세 중요도시까지의 거리의 합이 최소인것이 답이다.
하지만 문제는 K가 3보다 클 경우이다.
K가 4일때는 위의 그림처럼 추가된 중요도시가 생기면서 붉은색 간선이 추가적으로 더해지는것을
피할 수 없다.
이것을 어떻게 해결해야할까?
두 중요도시로부터 어느 정점의 거리를 구해서 이를 이용하면 해결할 수 있다.
두 중요도시로부터 정점$i$의 거리를 $dist2[u][v][i]$라 하자.
$dist2$은 위에서 말한 붉은색 간선이 추가적으로 더해지는것을 피할 수 있게 된다.
따라서 K는 3일때처럼 N번 탐색하여 최솟값을 구할 수 있게된다.
K는 4일때를 보면 $dist2[u][v][i]$의 두 묶음으로 생각할 수 있다.
$\min_{i=1}^{N}$($dist2[per[0]][per[1]][i] + dist2[per[2]][per[3]][i]$)
K는 5일때는 남는 한개까지 포함시켜 구하면 된다.
$\min_{i=1}^{N}$($dist2[per[0]][per[1]][i] + dist2[per[2]][per[3]][i] + dist[per[4]][i]$)
위의 index로 들어가는 $per[]$는 permutation value이다.
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mp(a,b) make_pair(a,b)
#define INF (ll)9e18
int N, K, M;
int impo[5];
vector<pair<ll, int>> adj[100001];
ll dist1[5][100001];
ll dist2[5][5][100001];
void dijkstra(int index) {
priority_queue<pair<ll, int>> pq;
dist1[index][impo[index]] = 0;
pq.push(mp(0, impo[index]));
while (!pq.empty()) {
int here = pq.top().second;
ll cost = -pq.top().first;
pq.pop();
if (dist1[index][here] < cost) continue;
for (auto const &n : adj[here]) {
int next = n.second;
ll ncost = n.first + cost;
if (dist1[index][next] > ncost) {
dist1[index][next] = ncost;
pq.push(mp(-ncost, next));
}
}
}
}
void dijkstra2(int u, int v) {
priority_queue<pair<ll, int>> pq;
for (int n = 1;n <= N;n++) {
pq.push(mp(-dist1[u][n] - dist1[v][n], n));
dist2[u][v][n] = dist1[u][n] + dist1[v][n];
}
while (!pq.empty()) {
int here = pq.top().second;
ll cost = -pq.top().first;
pq.pop();
if (dist2[u][v][here] < cost) continue;
for (auto const &n : adj[here]) {
int next = n.second;
ll ncost = cost + n.first;
if (dist2[u][v][next] > ncost) {
dist2[u][v][next] = ncost;
pq.push(mp(-ncost, next));
}
}
}
}
ll solve1(int *per) {
ll ret = INF;
for (int n = 1;n <= N;n++)
ret = min(ret, dist2[per[0]][per[1]][n] + dist2[per[2]][per[3]][n]);
return ret;
}
ll solve2(int *per) {
ll ret = INF;
for (int n = 1;n <= N;n++)
ret = min(ret, dist2[per[0]][per[1]][n] + dist2[per[2]][per[3]][n] + dist1[per[4]][n]);
return ret;
}
int main() {
memset(dist1, 0x3f, sizeof dist1);
scanf("%d%d%d", &N, &K, &M);
for (int k = 0;k < K;k++) scanf("%d", &impo[k]);
sort(impo, impo + K);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].emplace_back(mp((ll)d, v));
adj[v].emplace_back(mp((ll)d, u));
}
for (int k = 0;k < K;k++)
dijkstra(k);
if (K == 2) {
printf("%lld\n", dist1[0][impo[1]]);
}
else if (K == 3) {
ll ans = INF;
for (int n = 1;n <= N;n++)
ans = min(ans, dist1[0][n] + dist1[1][n] + dist1[2][n]);
printf("%lld\n", ans);
}
else if (K == 4) {
for (int u = 0;u < K;u++) {
for (int v = u + 1;v < K;v++) {
dijkstra2(u, v);
}
}
ll ans = INF;
int per[4] = { 0,1,2,3 };
do {
if (per[0] < per[1] && per[2] < per[3])
ans = min(ans, solve1(per));
} while (next_permutation(per, per + 4));
printf("%lld\n", ans);
}
else if (K == 5) {
for (int u = 0;u < K;u++) {
for (int v = u + 1;v < K;v++) {
dijkstra2(u, v);
}
}
ll ans = INF;
int per[5] = { 0,1,2,3,4 };
do {
if (per[0] < per[1] && per[2] < per[3])
ans = min(ans, solve2(per));
} while (next_permutation(per, per + 5));
printf("%lld\n", ans);
}
return 0;
}
| cs |
회사에서 퇴근을 하는데 정체되는 시간 [S, E]가 주어진다.
도로는 거리1당 시간이 1씩 소모되는데 이 도로가 정체되는 도로이면서 정체 시간이라면
시간이 2씩 소모가 된다.
집에 도착했을 때 가장 늦게 도착하는 시간을 구하는 문제이다.
문제가 신호등 문제와 비슷하다.
정체되는 도로일 때 총 4가지의 경우만 비교해주면 되고 나머지는 일반적인 dijkstra이다.
1. 현재 시간이 S보다 작은 경우
1) 도로를 건너면서 시간이 S보다 커지는 경우
2) 도로를 건너도 시간이 S보다 작거나 같은 경우 (정체구간)
2. 현재 시간이 S보다 크거나 같은 경우
1) 현재 시간이 E보다 크거나 같은 경우
2) 현재 시간이 E보다 작은 경우 (정체구간)
위의 조건에서 1-2)와 2-2)의 조건만 잘 처리해주면 된다.
또한 이 문제의 중요한점이 맞는 풀이임에도 double형으로 풀었다면
부동소수점 오차때문에 AC를 받는다.
따라서 2배 뻥튀기를 해준 후 나중에 다시 2로 나눠 주면 된다.
(처음에 double형으로 풀었고 조건 하나 실수했었다.)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF (long long)1e18
int N, M;
long long S, E;
struct Home {
int v;
long long len;
bool stock;
Home() {}
Home(int vv, long long ll, bool ss) :v(vv), len(ll), stock(ss) {}
};
vector<Home> adj[5001];
long long dijkstra(int start) {
vector<long long> dist(N + 1, INF);
priority_queue<pair<long long, int>> pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty()) {
int here = pq.top().second;
long long cost = -pq.top().first;
pq.pop();
if (dist[here] < cost) continue;
for (auto const &n : adj[here]) {
int next = n.v;
long long len = n.len;
if (n.stock) {
long long ncost;
if (dist[here] < S) {
if (dist[here] + len >= S) {
long long diff = S - dist[here]; //S시간보다 작을 때 일반속도로 감
long long last = len - diff;
long long st = min(E - S, last * 2); //S시간이상 E시간 미만일때 정체속도
long long fin = last - st / 2; //E시간보다 커졌을 때 일반속도
ncost = dist[here] + diff + st + fin;
}
else {
ncost = dist[here] + len;
}
}
else {
if (dist[here] >= E) {
ncost = dist[here] + len;
}
else {
long long st = min(E - dist[here], len * 2);
long long last = len - st / 2;
ncost = dist[here] + st + last;
}
}
if (dist[next] > ncost) {
dist[next] = ncost;
pq.push({ -ncost,next });
}
}
else {
long long ncost = dist[here] + len;
if (dist[next] > ncost) {
dist[next] = ncost;
pq.push({ -ncost,next });
}
}
}
}
long long ret = 0;
for (int n = 1;n <= N;n++) {
ret = max(ret, dist[n]);
}
return ret;
}
int main() {
scanf("%d%d%lld%lld", &N, &M, &S, &E);
S *= 2, E *= 2;
for (int m = 0;m < M;m++) {
int u, v, l, t1, t2;
scanf("%d%d%d%d%d", &u, &v, &l, &t1, &t2);
adj[u].emplace_back(Home(v, (long long)l*2, t1));
adj[v].emplace_back(Home(u, (long long)l*2, t2));
}
long long ans = dijkstra(1);
if (ans & 1) printf("%lld.5\n", ans / 2);
else printf("%lld\n", ans / 2);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기