문제: icpc.me/5719
BOJ 5719
다익스트라로 최단경로를 구현하고 최단경로에 포함되는 모든 간선들을 지워준 뒤 다시 다익스트라를 실행하면 된다.
최단경로에 속하는지 여부는 BFS처럼 처음에 queue에 도착지점을 넣어준 뒤 하나씩 빼면서
for(i 0~n-1) dp[here]= dp[i]+dist[i][here]를 만족하는 경우에 dist[i][here]를 지워주고 i를 큐에 삽입하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; int n, m, x, y, z, s, e; int a[502][502]; int dp[502]; void dijkstra() { memset(dp, -1, sizeof(dp)); priority_queue<pair<int, int>> pq; pq.push({ 0,s }); while (pq.size()) { int here = pq.top().second; int cost = -pq.top().first; pq.pop(); if (dp[here] != -1)continue; dp[here] = cost; for (int i = 0; i < n; i++) { if (a[here][i] == -1)continue; if (dp[i] != -1)continue; pq.push({ -cost - a[here][i],i }); } } } void eraseEdge() { queue<int> qu; qu.push(e); while (qu.size()) { int cx = qu.front(); qu.pop(); for (int i = 0; i < n; i++) { if (dp[cx] == dp[i] + a[i][cx] && a[i][cx] != -1) { a[i][cx] = -1; qu.push(i); } } } } int main() { scanf("%d%d", &n, &m); while (n != 0 && m != 0) { scanf("%d%d", &s, &e); memset(a, -1, sizeof(a)); for (int i = 0; i < m; i++) { scanf("%d%d%d", &x, &y, &z); a[x][y] = z; } dijkstra(); eraseEdge(); dijkstra(); printf("%d\n", dp[e]); scanf("%d%d", &n, &m); } return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)11895 속이기 (0) | 2017.01.03 |
---|---|
BOJ)2401 최대 문자열 붙여넣기 (1) | 2016.12.30 |
BOJ)13168 내일로 여행 (0) | 2016.12.30 |
BOJ)13911 집 구하기 (0) | 2016.12.30 |
BOJ 5719) 거의 최단 경로 (12) | 2016.12.29 |
BOJ 7894) 큰 숫자 (0) | 2016.12.29 |
코드 짱ㅇ 간결해요..! 헐ㄹ 이 문제 코드가 이렇게 짧을 수 있다니.... ((감탄하고 갑니다..!))
감사합니다 ㅎㅎ
Edge 어케 날릴까 고민하다가 왔습니다
한수배우고갑니다
자손형님
저보다잘하면다형님이십니다
erase 함수를 이용해서는 구현이안될까요 간선제거하는거
erase 함수를 이용하여서 삭제를 한다는건 아마 인접리스트로 그래프를 구현한 경우를 말하는것 같습니다. 벡터의 erase함수는 일정 구간을 삭제하는 함수라서 해당 문제에 적용시키기는 조금 소스가 복잡해질 것 같습니다. 인접 행렬을 통하여 구현하시면 편하게 구현하실 수 있을 것같습니다 ^^ ..
다익스트라 함수 코드안에서요.
if (dp[here] + a[here][i] < dp[i]) 조건문이 없어도 다익스트라가 성립하는 이유가 뭐에요?
계속 갱신해나가야 되는 거 아니에요?
힙을 이용한 다익스트라이기 때문에 저런 조건문을 안넣어도 항상 최적의 값이 갱신됩니다. 저 조건문대신 디피 배열을 갱신 할 때 이미 갱신된 값은 갱신없이 지나가는 조건문이 삽입됩니다
감사합니다
최단 경로에 포함되는 간선을 제거 한 후 다시 돌렸을 때 값이 이전에 구한 최단 경로 값과 동일 할 수 있지 않나요?
cx라는 변수명의 뜻이 있나요?
대단한 어프로치를 봤습니다. 감사합니다.