Codeground 캠퍼스와 도로(1) https://www.codeground.org/practice/practiceProblemView
Codeground 캠퍼스와 도로(2) https://www.codeground.org/practice/practiceProblemView
2325 개코전쟁 https://www.acmicpc.net/problem/2325
2307 도로검문 https://www.acmicpc.net/problem/2307
14554 The Other Way https://www.acmicpc.net/problem/14554
LG CNS 2017 Codemonster E번
어떤 지점으로부터의 최단거리를 알고싶으면 다익스트라 알고리즘을 사용하면 된다.
그 최단거리까지 이동하는 경로를 파악하는 방법은 2가지가 많이 사용된다.
1). 다익스트라 알고리즘이 끝나고 BFS돌리기
시작정점을 queue에 넣고 $dist[next]$ == $dist[here]$ + $adj[here][next]$인 경우에
queue를 삽입하는 것을 반복한다.
다익스트라 알고리즘자체에서 최단경로를 갱신하는 방법과 유사하다.
2). 다익스트라 알고리즘을 돌리며 저장하기
$dist[next]$ == $dist[here]$ + $adj[here][next]$인 경우에 prev배열에 저장한다.
$dist[next]$ > $dist[here]$ + $adj[here][next]$인 경우에는 새로 갱신됬을 수 있으니
prev배열을 초기화한 후 저장한다.
1. 5719 거의 최단경로
최단경로를 구해서 다 지운후 다음 최단경로를 구한다.
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M, S, D;
vector<vector<pair<int, int>>> adj, rev;
vector<vector<bool>> visit;
vector<int> dist;
void di(int start, int end){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
fill(dist.begin(), dist.end(), INF);
dist[start] = 0;
pq.push({ 0, start });
while (!pq.empty()){
int here = pq.top().second;
pq.pop();
for (auto n : adj[here]){
int next = n.second;
int cost = n.first + dist[here];
if (dist[next] > cost && visit[here][next]){
dist[next] = cost;
pq.push({ dist[next], next });
}
}
}
}
void bfs(int start, int end){
queue<int> q;
q.push(end);
while (!q.empty()){
int here = q.front();
q.pop();
if (here == start) continue;
for (auto n : rev[here]){
int next = n.second;
if (dist[here] == dist[next] + n.first){
visit[next][here] = false;
q.push(next);
}
}
}
}
int main(){
while (scanf("%d%d", &N, &M), !(N == 0 && M == 0)){
adj = vector<vector<pair<int, int> > >(N, vector<pair<int, int>>());
rev = vector<vector<pair<int, int> > >(N, vector<pair<int, int>>());
visit = vector<vector<bool> >(N, vector<bool>(N, true));
dist = vector<int>(N, INF);
scanf("%d%d", &S, &D);
for (int m = 0; m < M; m++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d, v });
rev[v].push_back({ d, u });
}
di(S, D);
bfs(S, D);
di(S, D);
if (dist[D] != INF) printf("%d\n", dist[D]);
else printf("-1\n");
}
return 0;
}
| cs |
2. 캠퍼스와 도로(1)
통행료를 징수하는 지점은 시작정점과 도착정점을 제외한 최단경로의 정점들이다.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define INF 987654321
int N, M;
int ans;
vector <vector<pair<int, int> > > adj; //cost, to
vector<int> dist;
vector<bool> visit;
void dijkstra(int start){
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
dist[start] = 0;
pq.push(make_pair(0, start));
while (!pq.empty()){
int here = pq.top().second;
pq.pop();
for (auto n : adj[here]){
int next = n.second;
int ncost = n.first + dist[here];
if (dist[next] > ncost){
dist[next] = ncost;
pq.push(make_pair(ncost, next));
}
}
}
}
void bfs(int start){
queue<int> q;
q.push(start);
while (!q.empty()){
int here = q.front();
q.pop();
for (auto n : adj[here]){
int next = n.second;
int cost = n.first;
if (dist[next] == dist[here] + cost){ // here까지 최단거리로 오고 next까지 최단거리로 한번 더 이동할 수 있다면
q.push(next);
if (here != start){
if (!visit[here]) ans++;
visit[here] = true; //통행료를 걷을 수 있는 지점
}
}
}
}
}
int main(){
setbuf(stdout, NULL);
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++){
ans = 0;
scanf("%d%d", &N, &M);
adj = vector<vector<pair<int, int> > >(N + 1);
visit = vector<bool>(N + 1, false);
for (int m = 0; m < M; m++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back(make_pair(d, v));
adj[v].push_back(make_pair(d, u));
}
for (int n = 1; n <= N; n++){
dist = vector<int>(N + 1, INF);
dijkstra(n);
bfs(n);
}
printf("Case #%d\n", t);
printf("%d ", N - ans);
for (int n = 1; n <= N; n++)
if (!visit[n])
printf("%d ", n);
printf("\n");
}
return 0;
}
| cs |
3. 캠퍼스와 도로(2)
이 문제때문에 글쓴거다. BFS방식 말고 prev배열에 저장하는 방식을 사용했는데
이 문제때문에 글쓴거다. BFS방식 말고 prev배열에 저장하는 방식을 사용했는데
거리가 갱신될때 prev를 초기화하지 않아서 틀렸다.
어떤정점 V를 갈 수 있는 최단경로가 2개이상 있을 때는 다른경로로 가면 되지만
한개뿐일때는 꼭 그 정점을 지나야 V를 가는데 최단거리가 된다.
따라서 정점 V를 가기위한 최단경로의 정점이 한개뿐일때의 정점들이 답이된다.
(단, 정점이 시작정점인 경우는 제외해야한다.)
(단, 정점이 시작정점인 경우는 제외해야한다.)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
#define INF 987654321
int N, M;
vector<vector<pair<int, int> > > adj;
vector<vector<int> > par;
vector<bool> visit;
void dijkstra(int start){
vector<int> dist(N + 1, INF);
par = vector<vector<int> >(N + 1, vector<int>());
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
dist[start] = 0;
pq.push(make_pair(0, start));
while (!pq.empty()){
int here = pq.top().second;
pq.pop();
for (auto n : adj[here]){
int next = n.second;
int ncost = dist[here] + n.first;
if (dist[next] > ncost){
dist[next] = ncost;
pq.push(make_pair(ncost, next));
par[next].clear();
par[next].push_back(here);
}
else if (dist[next] == ncost){
par[next].push_back(here);
}
}
}
for (int next = 1; next <= N; next++){
if (start != next && par[next].size() == 1){ //next까지 도달하는데 최단 경로가 한개(here->next 경로)밖에 없다면
int must = par[next][0];
if (must != start){
visit[must] = true;
}
}
}
}
int main(){
setbuf(stdout, NULL);
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++){
scanf("%d%d", &N, &M);
adj = vector < vector<pair<int, int> > >(N + 1);
visit = vector<bool>(N + 1, false);
for (int m = 0; m < M; m++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back(make_pair(d, v));
adj[v].push_back(make_pair(d, u));
}
int ans = 0;
for (int start = 1; start <= N; start++)
dijkstra(start);
for (int n = 1; n <= N; n++)
if (visit[n])
ans++;
printf("Case #%d\n", t);
printf("%d ", ans);
for (int n = 1; n <= N; n++)
if (visit[n]) printf("%d ", n);
printf("\n");
}
return 0;
}
| cs |
4. 개코전쟁, 도로검문
간선을 하나 삭제시켜 최단거리의 값이 최대인 거리를 구하는 문제이다.
핵심 풀이는 지워야 하는 간선은 간선을 삭제하지 않고 최단경로를 만드는 경로의 간선이라는 것이다.
당연하게도 최단경로가 아닌 간선을 지워봤자 최단경로는 변하지 않을 것이다.
또한 최단경로가 여러개있어도 한개의 최단경로만 파악해 놓아도 된다.
어떤 정점까지 가는 최단경로가 여러개 있다면 그 중 한개의 간선을 제거한다 해도 변하지 않거나
한 개의 최단 경로만 파악해 놓고 삭제한 결과랑 같기 때문이다.
이 문제를 처음엔 못풀었는데 위의 유도과정을 생각치 못한것 같다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int par[1001];
vector<pair<int,int>> adj[1001];
void dijkstra1() {
vector<int> dist(N + 1, INF);
priority_queue<pair<int, int>> pq;
fill(par, par + N + 1, -1);
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;
int ncost = n.first + cost;
if (dist[next] > ncost) {
dist[next] = ncost;
par[next] = here;
pq.push({ -ncost,next });
}
}
}
}
int dijkstra2(int notgo_u, int notgo_v) {
vector<int> dist(N + 1, INF);
priority_queue<pair<int, int>> pq;
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;
if ((here == notgo_u && next == notgo_v) || (here == notgo_v && next == notgo_u)) continue;
int ncost = n.first + cost;
if (dist[next] > ncost) {
dist[next] = ncost;
pq.push({ -ncost,next });
}
}
}
return dist[N];
}
int main() {
scanf("%d%d", &N, &M);
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 });
}
dijkstra1();
int ans = 0;
for (int i = N;;i = par[i]) {
ans = max(ans, dijkstra2(par[i], i));
if (par[i] == 1) break;
}
printf("%d\n", ans);
return 0;
}
| cs |
5. The Other Way
이것은 추적은 아니지만 지속적으로 갱신 및 저장하는것이 비슷해서 넣었다.
S에서 E로 가는 경우의 수를 구하는 문제이다.
DP를 이용하는데 먼저 소스를 올리겠다.
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#define INF 1987654321987654321
#define mod 1000000009
using namespace std;
int N, M;
vector<pair<int, int>> adj[100001];
int dp[100001];
long long dist[100001];
void dijkstra(int start, int end) {
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
fill(dist + 1, dist + N + 1, INF);
dist[start] = 0;
dp[start] = 1;
pq.push({ 0,start });
while (!pq.empty()) {
int here = pq.top().second;
long long hdist = pq.top().first;
pq.pop();
if (dist[here] ^ hdist) continue;
for (auto n : adj[here]) {
int next = n.second;
long long cost = (long long)n.first + dist[here];
if (dist[next] > cost) {
dp[next] = dp[here] % mod;
dist[next] = cost;
pq.push({ cost,next });
}
else if (dist[next] == cost) {
dp[next] += dp[here];
dp[next] %= mod;
}
}
}
}
int main() {
int s, e;
scanf("%d%d%d%d", &N, &M,&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 });
}
dijkstra(s,e);
printf("%d\n", dp[e]);
return 0;
}
| cs |
다익스트라 내부에 있는 if (dist[here] ^ hdist) continue; 이 코드 때문에 애를 먹었다.
(if (dist[here] < hdist) continue; 이렇게 써도 된다.)
바로 반례를 들자면
4 5 1 4
1 2 1
1 3 4
2 3 1
3 4 4
3 4 6ans : 1
If none of this sentence {if (dist[here] ^ hdist) continue;}, then : 2
나머지 부분은 충분히 이해가 되기때문에 생략한다.
6. LG CNS 2017 Codemonster E번
정확한 풀이인지는 채점을 하지 못해서 장담하지는 못한다.(박트리님 블로그를 참고하여 아마 맞는 풀이일듯)
// CNS 그래프는 기존 그래프의 최단경로를 유지하되 edge 가중치들의 합이 가장 작은 그래프이다.
// 정점과 방향성 있는 간선들의 정보들이 주어질때 CNS 그래프의 가중치의 합을 구하는 문제다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF (ll)(1e18)
int N, M;
vector<pair<ll, pair<int, int>>> adj[1111];
ll dist[1111];
vector<int> par[1111];
vector<int> edge[20001];
int cnt = 0;
vector<bool> visit;
void dijkstra(int start) {
memset(dist, 0x3f, sizeof dist);
priority_queue<pair<ll, int>> pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty()) {
int here = pq.top().second;
ll cost = -pq.top().first;
pq.pop();
if (dist[here] < cost) continue;
for (auto &n : adj[here]) {
int next = n.second.first;
ll ncost = n.first + dist[here];
if (dist[next] > ncost) {
dist[next] = ncost;
par[next].clear();
par[next].push_back(n.second.second);
pq.push({ -ncost,next });
}
else if (dist[next] == ncost) {
par[next].push_back(n.second.second);
}
}
}
for (int n = 1;n <= N;n++) {
if (par[n].empty()) continue;
for (int m = 0;m < par[n].size();++m) {
edge[par[n][m]].push_back(cnt);
}
cnt++;
}
}
int main() {
scanf("%d%d", &N, &M);
vector<pair<ll, int>> vadj;
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ (ll)d, {v, m} });
vadj.push_back({ (ll)d,m });
}
for (int n = 1;n <= N;n++)
dijkstra(n);
sort(vadj.begin(), vadj.end());
ll ans = 0;
visit.resize(cnt + 1, false);
for (int n = 0;n < vadj.size();++n) {
ll cost = vadj[n].first;
int idx = vadj[n].second;
bool flag = false;
for (int m = 0;m < edge[idx].size();++m) {
//이미 모두 방문했으면 이 간선으로 통하는 최단경로가 다 존재하므로
//이 간선을 추가시킬 필요가 없다.
if (!visit[edge[idx][m]]) flag = true;
}
if (flag) ans += cost;
for (int m = 0;m < edge[idx].size();++m) {
visit[edge[idx][m]] = true;
}
}
printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기