너와 나의 스토리

문제: https://www.acmicpc.net/problem/1865 소스 코드: #include #include #include #include #include #include #include #define inf 987654321 using namespace std; typedef pair P; vector adj; int tc, n, m, wf, dist[501]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc; while (tc--) { cin >> n >> m >> wf; bool chk = false; adj.clear(); adj.resize(n + 2); fill(dist, dist +..

문제: https://www.acmicpc.net/problem/10159 문제 풀이:- 플로이드 와샬 알고리즘 이용- 입력 값을 단방향으로 이동 가능하다고 생각 ex) 6 5 1 2 // 1->2로 이동 가능 2 3 // 2->3으로 이동 가능 3 4 // ... 5 4 6 5 - a->b로 못가고 b->a로도 못 가면 비교 못 하는 것 -> cnt++ 소스 코드: #include #include #include #include #include #define inf 1000000using namespace std; int n, k,dist[101][101]; int main() {ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL); cin >> n >..

문제: https://www.acmicpc.net/problem/9205 문제 풀이: - 처음에 플로이드 와샬로 풀었는데 틀렸다. 틀린 이유를 모르겠어서 그냥 bfs로 풀었다 ㅎㅎ - 거리가 1000이하로 차이 나는 곳들 다 queue에 넣다가 락 페스티벌까지 도달 했으면 check=true; 그렇지 않고 끝나버렸으면 "sad" 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-9205

문제: https://www.acmicpc.net/problem/13168 문제풀이: - map 이용해서 각 대중교통이름을 정수로 나타냄- 가야할 곳들 순서대로 vector에 삽입- 비용은 내일로 티켓 사용할 때와 사용하지 않을 때를 따로 저장. a->b 로 갈 수 있는 대중교통이 여러개이면 가장 작은 값으로 저장. (참고로 양방향) - 정해진 루트를 vector에 넣어둔 순서대로 dist 더해줌 // 그냥 순서대로 sum+=dist[v[0]][v[1]]; ~~~ 해주면 됨 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-13168

문제: https://www.acmicpc.net/problem/1956 문제 풀이: - 플로이드 와샬 알고리즘 사용- 자기 자신으로 가는 (dist[a][a]=INF) 거리도 INF로 초기화- 자기 자신으로 가는 거리가 INF가 아니면 사이클이 존재하는 것 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1956

문제: https://www.acmicpc.net/problem/2610 문제 풀이: - 플로이드 와샬 알고리즘 이용해서 dist 구하기 - bool check[101] 배열 이용해서 연결된 그룹 구분하여 vector에 저장 - 그룹별로 "의사전달시간 중 최댓값이 최소가 되도록" 대표 선정 (이거 이해 잘못해서 틀림 ㅎ) ㄴ 의사전달시간을 각 사람별로 다 더하는 것이 아니라 대표로부터 가장 멀리 떨어진 사람 (다른 사람을 가장 많이 거쳐야 하는 사람) 과의 거리 -> 의사전달시간 중 최댓값 가 최소인 사람을 대표로 선정 - 대표들을 vector에 저장해서 sort한 다음 작은 번호부터 출력 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa65993..

문제: https://www.acmicpc.net/problem/1613 문제 풀이: - 플로이드 와샬 알고리즘 이용 - 단방향이므로if( dist[a][b]!=INF ) -> a가 b보다 앞선 사건 (a->b로의 경로가 존재) else if( dist[b][a]!=INF ) -> b가 a보다 앞선 사건 (a->b로의 경로는 존재하지 않지만 b->a로의 경로는 존재) else -> 알 수 없음 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1613

문제: https://www.acmicpc.net/problem/1389 문제 풀이: - 자기 자신은 dist[a][a]=0;- 양방향이므로 dist[a][b]=1;dist[b][a]=1; - 그 외 INF로 채움 - 각 점에서의 케빈 베이컨 구해서 vector에 넣음- sort 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1389-6