풀이
다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데
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 <(edg a)const {
return dst > a.dst;
}
};
vector<edg> gph[100001];
void go(vector<ll> dp[], int f) {
priority_queue<edg> pq;
dp[0].resize(n+1); dp[1].resize(n+1);
for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = 1e17;
pq.push({ 1,0,0 });
dp[0][1] = 0;
while (!pq.empty()) {
edg now = pq.top(); pq.pop();
int c = now.cnt;
if (dp[c][now.idx] != now.dst) continue;
for (int i = 0; i < gph[now.idx].size(); i++) {
edg nxt = gph[now.idx][i];
ll *x = &dp[f?(c+1)%2:c][nxt.idx], y = dp[c][now.idx], z = nxt.dst;
z = f?c?z*2:z/2:z;
if (*x > y + z) {
*x = y + z;
pq.push({ nxt.idx,f?(c+1)%2:c,*x });
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
while (m--) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
gph[u].push_back({ v,0,w*2 });
gph[v].push_back({ u,0,w*2 });
}
vector<ll> r1[2], r2[2];
go(r1, 0); go(r2, 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (r1[0][i] < min(r2[0][i], r2[1][i])) ans++;
}
printf("%d ", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이