11569 신호등 https://www.acmicpc.net/problem/11569
13308 주유소 https://www.acmicpc.net/problem/13308
1162 도로포장 https://www.acmicpc.net/problem/1162
1854 K번째 최단경로 찾기 https://www.acmicpc.net/problem/1854
13907 세금 https://www.acmicpc.net/problem/13907
1. 두 개의 네비게이션
두 종류의 네비게이션이 있는데 현재 교차로에서 회사(1)까지 가는 최단경로가 아닌 경로인 경우
경보음이 울린다.
동현이가 회사(1)에서 집(N)으로 이동하는 경로중 가장 적은 횟수로 경보음이 울리는 경우의 횟수를
구하는 문제이다.
android, iphone인경우에 대해 dijkstra알고리즘으로 N에서 1까지 이동하면서 dist를 구해 놓는다.
$dist[here]$ != $dist[next]$ + $d[next][here]$인 지점은 현재 교차로에서 회사까지 가는 최단경로가
아닌지점으로 경보음을 하나씩 증가 시키며 Heap을 돌린다.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(mp(a,b),c)
#define INF 987654321
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> T;
int N, M;
vector<vector<T> > adj,rev_adj;
vector<int> and_dist, iph_dist;
void dijkstra(int start, const vector<vector<T>> &path, vector<int> &dist, bool flag){
//if(flag) : android, else : iphone
priority_queue<P, vector<P>, greater<P> > pq;
dist[start] = 0;
pq.push(mp(0, start));
while (!pq.empty()){
int here = pq.top().second;
pq.pop();
for (auto n : path[here]){
int next = n.second;
int ncost;
if (flag) ncost = n.first.first + dist[here];
else ncost = n.first.second + dist[here];
if (dist[next] > ncost){
dist[next] = ncost;
pq.push(mp(ncost, next));
}
}
}
}
int solve(int start){
priority_queue<P, vector<P>, greater<P> > pq;
vector<int> bell(N + 1, INF);
bell[start] = 0;
pq.push(mp(0, start));
while (!pq.empty()){
int here = pq.top().second;
if (here == N) return (pq.top().first);
pq.pop();
for (auto n : adj[here]){
int next = n.second;
int plus = 0;
if (and_dist[here] != and_dist[next] + n.first.first)
plus++;
if (iph_dist[here] != iph_dist[next] + n.first.second)
plus++;
if (bell[next] > bell[here] + plus){
bell[next] = bell[here] + plus;
pq.push(mp(bell[here] + plus, next));
}
}
}
return -1;
}
int main(){
setbuf(stdout, NULL);
int Test;
scanf("%d", &Test);
for (int t = 1; t <= Test; t++){
scanf("%d%d", &N, &M);
adj = vector<vector<T>>(N + 1, vector<T>());
rev_adj = vector<vector<T>>(N + 1, vector<T>());
and_dist = vector<int>(N + 1, INF);
iph_dist = vector<int>(N + 1, INF);
for (int m = 0; m < M; m++){
int u, v, A, I;
scanf("%d%d%d%d", &u, &v, &A, &I);
adj[u].push_back(mt(A, I, v));
rev_adj[v].push_back(mt(A, I, u));
}
dijkstra(N, rev_adj, and_dist, true);
dijkstra(N, rev_adj, iph_dist, false);
printf("#testcase%d\n", t);
printf("%d\n",solve(1));
}
return 0;
}
| cs |
2. 신호등
신호가 존재하는 경로들이 있을 때 목적지까지 도달하는데 최단시간을 구하는 문제이다.
신호를 잘 처리해주고 par[]배열로 이전 경로를 저장하는 대신 queue에 (from,to)를 넣어
이전경로를 대체해줘야 맞는 답이 나온다.
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, pair<int,int> > P;
#define INF 987654321987654321
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(a,mp(b,c))
int N, M, S, D;
vector<vector<pair<int,ll> > > adj; //정렬 되있음 next, cost
vector<int> delay; //교차로에서의 주기
ll dijkstra(int start, int end){
priority_queue<P, vector<P>, greater<P>> pq; //cost, from, here
vector<ll> dist(N + 1, INF);
dist[start] = 0;
//처음 start->ver 연결된 지점은 교차신호 상관없음
for (auto n : adj[start]){
pq.push(mt(n.second, start, n.first));
dist[n.first] = n.second;
}
while (!pq.empty()){
int here = pq.top().second.second;
int from = pq.top().second.first;
ll cost = pq.top().first;
pq.pop();
if (here == end) return dist[end];
for (auto n : adj[here]){
int next = n.first;
ll ncost = n.second;
//주기는 here교차로의 size에 의존함
//from -> here -> next ,from이 here교차로의 몇번째 order인지 알아야함
ll T = cost; //시간
ll P = delay[here]; //delay
ll size = adj[here].size();
int order; //가고자하는 패턴번호
for (order = 0; order < adj[here].size(); order++) //가고자하는 패턴번호를 구함
if (adj[here][order].first == from) break;
//최종 T를 구함
int curr = (T / P) % size; //현재 패턴번호
if (order != curr)
T = (T / P + (order + size - curr) % size) * P; //가장 근접한 T로 만듬
if (dist[next] > T + ncost){
dist[next] = T + ncost;
pq.push(mt(dist[next], here, next));
}
}
}
return dist[end];
}
int main(){
int T;
scanf("%d", &T);
while (T--){
scanf("%d%d%d%d", &N, &M, &S, &D);
adj = vector<vector<pair<int, ll> > >(N + 1);
delay = vector<int>(N + 1);
for (int m = 0; m < M; m++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back(mp(v, (ll)d));
adj[v].push_back(mp(u, (ll)d));
}
for (int n = 1; n <= N; n++){
scanf("%d", &delay[n]);
sort(adj[n].begin(), adj[n].end());
}
ll ans = dijkstra(S, D);
printf("%lld\n", ans == INF ? -1 : ans);
}
return 0;
}
|
3. 주유소
해결방법은 다음에 갈 주유소의 가격이 더 작아질때 까지는 기존의 가격으로 구입하고
아닐 때는 갱신해서 구입하면서 greedy하게 나가면 된다.
이 문제도 위와 같은 방식으로 하되 그래프의 형태이기 때문에 DP를 이용한다.
<13308 주유소 의식의 흐름>
1. 단순히 큐에 dist변수 하나만 넣고 돌려서 "메모리 초과" 발생
2. visit배열을 이용해 방문여부를 판단하며 돌리려 했으나 불가능함을 인식
3. 갱신될때마다 dist배열을 초기화후 돌려서 "시간 초과" 발생
4. 더이상 생각 못하다 결국 힌트를 얻음 -> dp형식으로
dist[N][std] : N까지 오는데 dist[N][std]원 소모, 기름당 가격 : std
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
#define INF 987654321
typedef pair<int, int> P;
typedef pair<long long, P> TP;
int N, M;
int cost[2501];
vector<pair<int, int>> adj[2501];
long long solve(int start, int end) {
vector<vector<long long>> dist(2502, vector<long long>(2502, INF));
priority_queue<TP, vector<TP>, greater<TP>> pq;
pq.push({ 0,{ cost[start],start } }); // dist, standard, next
while (!pq.empty()) {
int here = pq.top().second.second;
int std = pq.top().second.first;
long long d = pq.top().first;
pq.pop();
if (here == end) return d;
if (dist[here][std] != INF) continue;
dist[here][std] = d;
for (auto n : adj[here]) {
int next = n.second;
long long ndist = d + std*n.first;
if (dist[next][min(std, cost[next])] == INF) {
pq.push({ ndist,{ min(std,cost[next]), next } });
}
}
}
return -1;
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d,v });
adj[v].push_back({ d,u });
}
printf("%lld\n", solve(1, N));
return 0;
}
| cs |
4. 도로포장
1번정점에서 N번정점으로 이동하는데 최소시간을 구하는데 최대 K개의 간선의
cost를 0으로 처리할 수 있다.
Dijkstra DP로 풀 수 있다.
queue에 이전에 온 정점을 넣어서 왕복처리되지 않게 최적화 시켰는데 별 상관없다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321987654321
int N, M, K;
vector<pair<long long, int>> adj[10001];
long long dist[10001][21];
long long dijkstra(int start, int end) {
long long ret = INF;
priority_queue<pair<pair<long long, int>,pair<int,int>>> pq; //dist, K, here, prev
for (int n = 2;n <= N;n++)
for (int k = 0;k <= K;k++)
dist[n][k] = INF;
pq.push({ {0,0},{start,-1} });
while (!pq.empty()) {
int here = pq.top().second.first;
int prev = pq.top().second.second;
int hK = pq.top().first.second;
long long cost = -pq.top().first.first;
pq.pop();
if (here == end) {
ret = min(ret, dist[here][hK]);
continue;
}
for (auto n : adj[here]) {
int next = n.second;
long long ncost = n.first + cost;
if (dist[next][hK] > ncost) {
dist[next][hK] = ncost;
pq.push({ {-ncost,hK}, {next,here} });
}
if (dist[next][hK + 1] > cost && hK + 1 <= K && next != prev) {
dist[next][hK + 1] = cost;
pq.push({ { -cost,hK + 1 },{next, here} });
}
}
}
return ret;
}
int main() {
scanf("%d%d%d", &N, &M, &K);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d,v });
adj[v].push_back({ d,u });
}
long long ans = dijkstra(1, N);
printf("%lld\n", ans);
return 0;
}
| cs |
5. K번째 최단경로 찾기
1번 도시에서 다른 도시들로 갈때 K번째 최단경로를 찾는 문제이다.
처음에는 정점을 K번째 까지 오는것만으로 조건을 주어서 풀었는데 시간이 오래걸렸다.
정점에 돌아온 정보를 Max Heap에 저장시켜서 갱신시켜주면 된다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 2147483647
int N, M, K;
vector<pair<int,pair<int, int>>> adj[1001];
priority_queue<pair<int, int>> pq;
void dijkstra() {
priority_queue<int> dist[1001];
dist[1].push(0);
pq.push({ 0,1 });
while (!pq.empty()) {
int here = pq.top().second;
int cost = -pq.top().first;
pq.pop();
for (auto n : adj[here]) {
int next = n.second.second;
int ncost = n.second.first + cost;
if (dist[next].size() < K) {
dist[next].push(ncost);
pq.push({ -ncost,next });
}
else {
if (dist[next].top() > ncost) {
dist[next].pop();
dist[next].push(ncost);
pq.push({ -ncost,next });
}
}
}
}
for (int n = 1;n <= N;n++) {
if (dist[n].size() < K) printf("-1\n");
else printf("%d\n", dist[n].top());
}
}
int main() {
scanf("%d%d%d", &N, &M, &K);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ m,{ d,v } });
}
dijkstra();
return 0;
}
| cs |
6. 세금
각 도로마다 통행료가 있다.
세금이 오르면 오른 세금만큼 모든 도로의 통행료가 오른다.
K번 세금이 오를때 S에서 D로 이동하는 최소통행료를 구하는 문제다.
K번마다 오른 세금으로 dijkstra를 돌리면 당연히 TLE가 나온다.
dp형식으로 S에서 도달하는 정점V에 대해 거쳐온 도로 수도 저장해준다.
정점이 N개있으니 어떠한 정점V로 가는데 거쳐온 도로 수도 최대 N개가 된다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
#define INF 987654321987654321
typedef long long ll;
typedef pair<pair<ll,int>, int> P; //dist, edge cnt, vertex
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(mp(a,b),c)
int N, M, K;
int S, E;
vector<pair<int, int>> adj[1001];
ll dist[1001][1001];
void dijkstra(ll &first) {
for (int n = 1;n <= N;n++)
for (int m = 0;m < 1001;m++) dist[n][m] = INF;
priority_queue<P, vector<P>, greater<P>> pq;
dist[S][0] = 0;
pq.push(mt(0, 0, S));
while (!pq.empty()) {
int here = pq.top().second;
int cnt = pq.top().first.second;
ll cost = pq.top().first.first;
pq.pop();
bool find = false;
for (int i = 0;i < cnt;i++) {
if (dist[here][i] < cost) {
find = true;
break;
}
}
if (find || dist[here][cnt] < cost) continue;
if (here == E) {
first = min(first, dist[here][cnt]);
continue;
}
for (auto n : adj[here]) {
int next = n.second;
ll ncost = (ll)n.first;
if (cnt + 1 <= N && dist[next][cnt + 1] > dist[here][cnt] + ncost) {
dist[next][cnt + 1] = dist[here][cnt] + ncost;
pq.push(mt(dist[next][cnt + 1], cnt + 1, next));
}
}
}
}
int main() {
scanf("%d%d%d", &N, &M, &K);
scanf("%d%d", &S, &E);
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d,v });
adj[v].push_back({ d,u });
}
ll first = INF;
dijkstra(first);
printf("%lld\n", first);
vector<pair<ll,ll>> re;
for (int e = 1;e <= N;e++) {
if (dist[E][e] != INF) {
re.push_back(mp(dist[E][e], (ll)e));
}
}
ll sum_tax = 0, tax;
for (int k = 0;k < K;k++) {
scanf("%lld", &tax);
sum_tax += tax;
ll ret = INF;
for (auto n : re) {
ret = min(ret, n.first + n.second*sum_tax);
}
printf("%lld\n", ret);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기