먼저 이 문제에 대해 AC를 못받았다
하지만 풀이를 생각해 냈고, 그게 올바른 풀이라는 것도 2주에 거쳐 확인했다(기간만 1달...)
심지어 나와 같은 풀이방법으로 구현해낸 다른 사람의 코드로 AC를 받았는데 내 코드만은 MLE가 나오는 상황이다
그러니까 정리하자면
1. 올바르게 문제를 푼 줄 알았는데 틀렸다
2. 잘 못 푼줄알고 2주가까이 검증했다
3. 그런데 다른사람의 풀이를 결국 봤는데 나랑 같았다
4. 그래서 그 분도 잘못풀었겠지 싶어 복붙해서 서밋했는데 AC가 나왔다
5. 멘붕와서 어제부터 잠못자고 유령상태다.... 왜 맞은걸까? 나는 왜 틀린걸까? 무한 반복....
무한 반복중인 상황을 나름 정리해보자면
1. 메모리 초과를 받았으니 배열 선언부분을 확인해보자! -> 올바르네ㅎㅎ, 똑같음을 확인
2. 다익스트라 구현에서 어디 미스를 낸건가? 배열 인덱싱에서 미스내면 MLE가 나오나? -> 인덱싱 미스는 런타임에러
3. 문제에 제시된 메모리 용량이 너무 작은건가? -> 평범함 256mb
4. 너무 많은 인클루드문과 매크로문을 적어놨나? -> 싹지워도 MLE 뚜들겨 맞음
5. 나와 같은 문제를 겪는 질문글을 찾아보자 -> 구글링해도 한개가 안나옴....
6. 나를 도와줄 사람을 찾자 -> 질문글에 대한 썰렁한 반응
7. AC받은 코드와 A to Z 비교를 해보자 -> 차이가 없음 풀이는 완전 같고, 구현도 같은 자료구조, 같은 로직으로 돌아감
8. 내가 모르는 cin, cout 등에서 잡아먹는 메모리가 있는건가? -> print문으로 바꿔도 MLE....
돌아버리겠는데 이렇게 블로그에 글로 남기면 언젠가 미래의 나가 해결 해주리라 굳게 믿고 있다
언제나 그렇듯 공부 계속 하다보면 잘해지고, 그때 다시보면 쉬워지고
이 문제도 같은 싸이클안에 포함일거라 믿는다😭
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
using namespace std;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define vt vector
#define pb push_back
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (n); i++)
//int INF = numeric_limits<int>::max();
#define INF 987654321
//const int num=1001;
vt<pii> adj[1001];
int par[1001];
int n,m;
void dij() {
vector<int> dist(n+1, INF);
fill(par, par+n+1, -1);dist[1]=0;
priority_queue<pii> pq;
pq.push({0, 1});
while (!pq.empty()) {
int now = pq.top().Y;
int cost = -pq.top().X;
pq.pop();
for (auto i: adj[now]) {
int nxt = i.Y;
int nxtcost = i.X+cost;
if (nxtcost > dist[nxt]) continue;
dist[nxt] = nxtcost;
par[nxt]=now;
pq.push({-nxtcost, nxt});
}
}
}
int dij2(int a, int b) {
vector<int> dist(n+1, INF);
priority_queue<pii> pq;
pq.push({0, 1});dist[1]=0;
while (!pq.empty()) {
int now = pq.top().Y;
int cost = -pq.top().X;
pq.pop();
for (auto i: adj[now]) {
int nxt = i.Y;
if ((now==a&&nxt==b)||(now==b&&nxt==a)) continue;
int nxtcost = i.X+cost;
if (nxtcost > dist[nxt]) continue;
dist[nxt] = nxtcost;
pq.push({-nxtcost, nxt});
}
}
return dist[n];
}
int main(void) {
fast_cin();
cin >> n >> m;
rep(i, m) {
int u,v,w;
cin >> u >> v >> w;
adj[u].pb({w, v});
adj[v].pb({w, u});
}
dij();
int ans=0;
for(int i=n;;i=par[i]) {
ans=max(ans, dij2(par[i], i));
if (par[i]==1) break;
}
cout << ans;
return 0;
}
'CodeReview' 카테고리의 다른 글
BOJ 1202 보석도둑 (0) | 2021.01.02 |
---|---|
개코 전쟁 (승리!) (0) | 2020.12.24 |
백준 개코전쟁(진짜 전쟁중, 치열함) (0) | 2020.12.23 |
templates for cp (0) | 2020.09.01 |
2020 GoogleKickStart Round E CodeReview (0) | 2020.08.25 |