-
[BOJ] 16167 : A Great Way
16167 : A Great Way 풀이 잘 짜주면 된다. 코드 #include <cstdio> #include <queue> #include <vector> #define fst first #define snd second using namespace std; int n, m; struct abc { int idx, cst; }; vector<abc> gph[101]; pair<int, int> dp[101]; int main() { scanf("%d %d", &n, &m); while (m--) { int a, b, c, d, e; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); if (e > 10) c += ((e-10)*d); gph[a].push_back({ b,c...
-
[BOJ] 16166 : 서울의 지하철
16166 : 서울의 지하철 풀이 잘 짜주면 된다. 비트마스크 썼다. 코드 #include <cstdio> #include <queue> #include <map> using namespace std; int n, en; struct abc { int idx, hosun, cnt; bool operator <(abc a)const { return cnt > a.cnt; } }; map<pair<int, int>, int> cnt; map<int, int> subway; int main() { scanf("%d", &n); for (int i = 1, k; i <= n; i++) { scanf("%d", &k); for (int j = 0, x; j < k;...
-
[BOJ] 16118 : 달빛 여우
16118 : 달빛 여우 풀이 다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데 if (dp[now] != current_sum) continue; 위와 같은 동작을 넣은 코드와 그렇지 않은 코드의 시간복잡도가 다르다. (자세히는 모름) 이 문제의 경우, 데이터가 엄청 빡세서 저 동작을 넣어주지 않으면 시간 초과를 받게 된다. 아래의 코드를 참고하자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; int n, m; struct edg { int idx, cnt; ll dst; bool operator...
-
[BOJ] 4485 : 녹색 옷 입은 애가 젤다지?
4485 : 녹색 옷 입은 애가 젤다지? 풀이 lulu lala 코드 #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, t, x, a[133][133], d[133][133]; struct abc { int x, y, c; bool operator <(abc a)const { return c > a.c; } }; int main() { for (scanf("%d", &n); n; scanf("%d", &n)) { for (int i = 1; i <=...
-
[BOJ] 10282 : 해킹
10282 : 해킹 풀이 안녕하세요 다욱스트라입니다 코드 #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m, s; struct edg { int idx, dst; bool operator <(edg A)const { return dst > A.dst; } }; int main() { cin.tie(0); ios_base::sync_with_stdio(0); int tc; for (cin >> tc; tc; tc--) { cin >> n >> m >> s; vector<vector<edg> > gph(n+1); vector<int> dst(n+1, 1e9); priority_queue<edg> pq; for (int i = 0, u, v,...
-
[BOJ] 6118 : 숨바꼭질
6118 : 숨바꼭질 풀이 최단경로 가즈아~~~ 코드 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int n_ = 20000 + 2; int n, m, a, b, c, dst[n_]; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0, u, v; i < m; i++) { scanf("%d %d", &u, &v); gph[u].push_back(v); gph[v].push_back(u); } queue<int> que; que.push(1); while (!que.empty()) { int now = que.front(); que.pop(); for (int nxt :...
-
[BOJ] 11779 : 최소비용 구하기 2
11779 : 최소비용 구하기 2 풀이 다익스트라를 쓰면 된다! 대신 trace(=trc)배열을 만들어서 노드 i가 어디서 왔는지 저장해주고, 나중에 역으로 따라서 출력하면 된다. 코드 #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; const int n_ = 1e3 + 3; const int INF = 1e9; struct edg { int idx, dst; edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int n, m, trc[n_],...
-
[BOJ] 1261 : 알고스팟
1261 : 알고스팟 풀이 다익스트라를 변형해보자 dp랑 적당히 섞어보자 코드 #include <cstdio> #include <queue> using namespace std; const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; const int n_ = 100 + 5; struct edg { int x, y, w; bool operator <(edg A)const { return w > A.w; } }; int main() { int n, m, chk[n_][n_] = {}; char a[n_][n_]; priority_queue<edg> pq; scanf("%d %d\n", &m, &n); for (int i =...
-
[BOJ] 13308 : 주유소
13308 : 주유소 풀이 2016 koi 전국대회 2번 문제이다. 뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다. 음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다! 여기서 트릭(?)을 한 번 써보자. priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면 이미 지금보다 작은 값으로 방문했었음이 보장된다. 그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef...
-
[BOJ] 1162 : 도로포장
1162 : 도로포장 풀이 dp[노드번호i][포장갯수k]로 놓고 다익스트라를 돌리자! 원래 다익스트라에서 사용하던 dist[i]대신 dp[i][j]를 참조하면서 돌면 된다. now.dst는 지금까지 누적해 온 dst값이고, nxt.dst는 노드 사이의 거리(가중치)이다. 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int n_ = 10000 + 1; struct edg { int idx, dst, cnt; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool...
-
[BOJ] 1753 : 최단경로
1753 : 최단경로 풀이 다익스트라를 짜자 우선순위 큐를 쓰자 코드 #include <stdio.h> #include <algorithm> #include <queue> #include <vector> using namespace std; const int v_ = 20000 + 1; const int INF = 987654321; struct edg { int idx, dst; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int v, e, s, dst[v_]; vector<edg> gph[v_]; void dijkstra() { for (int i = 0;...