1. 한 바퀴 돌린다.

2. 한 바퀴 더 돌리면서는 업데이트 될 때마다, 무한대로 설정한다.

3. 그걸로 출력

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1219
* BOJ 백준온라인져지 1219 오민식의 고민 풀이
*/
struct Edge {
int s, e, pr;
};
using namespace std;
long long INF = 2147483647L * 214214214;
int main () {
int N, startCity, endCity, M;
scanf("%d%d%d%d", &N, &startCity, &endCity, &M);
long long *d = new long long[N];
long long *p = new long long[N];
for (int i = 0; i < N; i++) {
d[i] = -INF;
}
Edge edge;
vector<Edge> edges;
for (int i = 0; i < M; i++) {
int S, E, P;
scanf("%d%d%d", &S, &E, &P);
edge.s = S; edge.e = E; edge.pr = -P;
edges.push_back(edge);
}
for (int i = 0; i < N; i++) {
scanf("%lld", &p[i]);
}
d[startCity] = p[startCity];
bool gee = false;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int s = edges[j].s; int e = edges[j].e; int pr = edges[j].pr;
if (d[s] == -INF) continue;
else if (d[s] == INF) d[e] = INF;
else if (d[e] < d[s] + p[e] + pr) {
d[e] = d[s] + p[e] + pr;
if (k) d[e] = INF;
}
}
}
}
if (d[endCity] == -INF) printf("gg");
else if (d[endCity] == INF) printf("Gee");
else printf("%lld", d[endCity]);
}
view raw BOJ_1219.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 4963 섬의 개수 풀이  (0) 2018.02.13
BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.


내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1865
* BOJ 백준온라인져지 1865 웜홀 풀이
*/
using namespace std;
int N, M;
int main () {
int T;
scanf("%d", &T);
while(T--) {
int N, M, W;
scanf("%d%d%d", &N, &M, &W);
int *d = new int[501];
vector<vector<pair<int, int> > > edges(N + 1);
for (int i = 0; i < 501; i++) {
d[i] = 987654321;
}
d[1] = 0;
for (int i = 0; i < M; i++) {
int S, E, T;
scanf("%d%d%d", &S, &E, &T);
edges[S].push_back(make_pair(E, T));
edges[E].push_back(make_pair(S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
scanf("%d%d%d", &S, &E, &T);
edges[S].push_back(make_pair(E, -T));
}
bool update = true;
int cnt = 0;
while (update && cnt != N) {
cnt++;
update = false;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < edges[i].size(); j++) {
if (d[edges[i][j].first] > d[i] + edges[i][j].second) {
d[edges[i][j].first] = d[i] + edges[i][j].second;
update = true;
}
}
}
}
printf("%s\n", cnt == N ? "YES" : "NO");
}
}
view raw BOJ_1865.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01
BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이  (0) 2018.01.30
음..

DP로 풀었다. 계단문제랑 비슷하다.


처음에는 그냥 3나눠지면 3하고 2되면 2하고 했는데, 그게 아니라 경우의수가 최소일 때 를 구하는것 이였다.

import java.io.*;
import java.util.*;
/**
* BOJ 12852 1로 만들기 2
* https://gist.github.com/KSH-code/97ac76b0518de5a02806170c11ab1a57
*/
public class Main{
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int dp[][] = new int[(int)(1e+6)+1][2];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i = 0; i<dp.length; i++){
dp[i][0] = Integer.MAX_VALUE;
}
dp[N][0] = 0;
calc(N);
bw.write(dp[1][0] + "\n");
Stack<Integer> list = new Stack<>();
int i = 1;
if(N == 2){
bw.write("2 ");
}else{
while(list.size() != dp[1][0]){
list.push(i = dp[i][1]);
}
while(!list.isEmpty()){
bw.write(list.pop() + " ");
}
}
bw.write("1");
bw.flush();
}
private static void calc(int N) throws IOException {
if(N == 1){
return;
}
if(N % 3 == 0){
if(dp[N / 3][0] >= dp[N][0] + 1){
dp[N / 3][0] = dp[N][0] + 1;
dp[N / 3][1] = N;
calc(N / 3);
}
}
if(N % 2 == 0){
if(dp[N / 2][0] >= dp[N][0] + 1){
dp[N / 2][0] = dp[N][0] + 1;
dp[N / 2][1] = N;
calc(N / 2);
}
}
if(dp[N - 1][0] >= dp[N][0] + 1){
dp[N - 1][0] = dp[N][0] + 1;
dp[N - 1][1] = N;
calc(N - 1);
}
}
}
view raw Main.java hosted with ❤ by GitHub

그래서 메모이제이션이랑 Stack을 이용해서 경로구하는거 까지 구현했다.


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 2042 구간 합 구하기 풀이  (0) 2017.10.24
BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번)  (0) 2017.10.23
2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번)  (0) 2017.10.20
BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선)  (0) 2017.10.19
BOJ 11657 타임머신 풀이 벨만 포드  (0) 2017.10.19
벨만포드 알고리즘을 처음 사용해봤다.

벨만포드는 다익스트라보다 느리고, 비슷하다.

다익스트라랑 다른 점은 음수가중치가 존재해도 사용이 가능하다는 것이다.

그런데 다익스트라보다 시간복잡도가 O(VE)로 크다. 다익스트라는 O(ElgV)

import java.io.*;
import java.util.*;
/**
* BOJ 11657 타임머신
* https://gist.github.com/KSH-code/db82f6fce9c81d50ce203417a159206a
*/
class Bus{
public int s, e ,w;
public Bus(int s, int e, int w) {
this.s = s;
this.e = e;
this.w = w;
}
}
public class Main{
private static final int MAX = 124124124;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1[] = br.readLine().split(" ");
int N = Integer.parseInt(str1[0]);
int M = Integer.parseInt(str1[1]);
Bus bus[] = new Bus[M];
int dist[] = new int[N+1];
Arrays.fill(dist, MAX);
dist[1] = 0;
for(int i = 0; i<M; i++){
String str2[] = br.readLine().split(" ");
int u = Integer.parseInt(str2[0]);
int v = Integer.parseInt(str2[1]);
int w = Integer.parseInt(str2[2]);
bus[i] = new Bus(u, v, w);
}
if(BellmanFord(dist, bus, N, M)){
for (int i = 2; i <=N; i++){
System.out.println(dist[i] == MAX ? -1 : dist[i]);
}
}else{
System.out.println(-1);
}
}
private static boolean BellmanFord(int dist[], Bus bus[], int N, int M){
for(int i = 1; i<=N; i++){
for(int j = 0; j<M; j++){
if(dist[bus[j].e] > bus[j].w + dist[bus[j].s]){
dist[bus[j].e] = bus[j].w + dist[bus[j].s];
}
}
}
for (int i = 0; i<M; i++)
if(dist[bus[i].e] > bus[i].w + dist[bus[i].s])
return false;
return true;
}
}
view raw Main.java hosted with ❤ by GitHub



저작자표시

'IT > 알고리즘' 카테고리의 다른 글

2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번)  (0) 2017.10.20
BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선)  (0) 2017.10.19
BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18

+ Recent posts

티스토리툴바