Notice
Recent Posts
Recent Comments
tony9402
[백준 11657] 타임머신 본문
반응형
백준 11657 타임머신
SPFA 공부중.... 벨만 포드랑 비슷하면서 살짝 다른 알고리즘
저번에 디피로 풀면 쉽게 풀리는 문제를 그냥 대충 BFS로 풀었는데 어떤 갓분이 그거 SPFA라고 하셔서 이번에 한번 공부해봄
그땐 음수가 없었기 때문에 사이클을 체크 하는 부분이 없어도 되지만 이 문젠 음수가 존재하여 음수 사이클 존재여부를 체크 해야함
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; queue<int> q; vector<vector<pair<int, int>>> map; vector<bool> InQ; vector<int> cycle; vector<int> ans; const int INF = 0x3f3f3f3f; int main() { int n, m; scanf("%d %d", &n, &m); InQ.resize(n + 1); cycle.resize(n + 1); map.resize(n + 1); ans.resize(n + 1); fill(ans.begin(), ans.end(), INF); fill(InQ.begin(), InQ.end(), false); fill(cycle.begin(), cycle.end(), false); int from, to, cost; for (int i = 0; i < m; i++) { scanf("%d %d %d", &from, &to, &cost); int j; for (j = 0; j < map[from].size(); j++) { if (map[from][j].first == to && map[from][j].second > cost) { map[from][j].second = cost; break; } } if(j==map[from].size())map[from].push_back(make_pair(to, cost)); } q.push(1); InQ[1] = true; cycle[1]++; ans[1] = 0; while (!q.empty()) { int now = q.front(); q.pop(); InQ[now] = false; for (int i = 0; i < map[now].size();i++) { int cost = map[now][i].second + ans[now]; if (cost < ans[map[now][i].first]) { ans[map[now][i].first] = cost; if (!InQ[map[now][i].first]) { cycle[map[now][i].first]++; if (cycle[map[now][i].first] >= n) { printf("-1"); return 0; } q.push(map[now][i].first); InQ[map[now][i].first] = true; } } } } for (int i = 2; i <= n; i++) { if (ans[i] == INF)printf("-1\n"); else printf("%d\n", ans[i]); } return 0; } | cs |
반응형
'알고리즘 > Baekjoon Online Judge' 카테고리의 다른 글
[백준 5656] 비교 연산자 (0) | 2018.10.20 |
---|---|
[백준 1182] 부분집합의 합 (0) | 2018.10.20 |
[백준 1504] 특정한 최단 경로 (0) | 2018.08.31 |
[백준 1753] 최단경로 (0) | 2018.08.31 |
[백준 1916] 최소비용 구하기 (0) | 2018.08.31 |
Comments