728x90
728x90
솔루션 1.
더보기
모든 정점 사이의 최단 경로를 구한 다음 그래프 DP를 수행하면서 "합리적인 이동경로"를 탐색하면 간단하게 AC를 받을 수 있다.
전체 코드
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
80
81
82
83
84
85
|
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
int n, m;
int dist[1001][1001];
int dp[1001];
int dijkstra(int start, graph &al);
int memo(int v, graph &al);
int main()
{
memset(dp, -1, sizeof dp);
fill(&dist[0][0], &dist[0][0] + 1001 * 1001, numeric_limits<int>::max());
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
graph adj(n + 1);
for (int i = 0; i < m; ++i)
{
int go, to, fee;
cin >> go >> to >> fee;
adj[go].push_back({to, fee});
adj[to].push_back({go, fee});
}
for (int i = 1; i <= n; ++i)
dijkstra(i, adj);
cout << memo(1, adj);
}
int dijkstra(int start, graph &al)
{
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
dist[start][start] = 0;
while (pq.size())
{
auto cur = pq.top();
pq.pop();
if (cur.first > dist[start][cur.second])
continue;
for (auto item: al[cur.second])
{
int ndist = cur.first + item.second;
if (ndist < dist[start][item.first])
{
dist[start][item.first] = ndist;
pq.push({ndist, item.first});
}
}
}
return dist[start][2];
}
int memo(int v, graph &al)
{
if (v == 2)
return 1;
int &ret = dp[v];
if (ret != -1)
return ret;
ret = 0;
for (auto item: al[v])
if (dist[v][2] > dist[item.first][2])
ret += memo(item.first, al);
return ret;
}
|
cs |
솔루션 2.
더보기
DP를 최단 경로를 탐색하면서 수행한다.
다익스트라를 기준으로 설명한다.
다음 dp 테이블을 최단 경로를 찾아가면서 채울 것이다.
dp[i] = i번 노드에서 출발하는 합리적인 이동경로의 수
거꾸로 도착점 2번 노드부터 탐색을 시작한다.
각 정점까지의 최단 경로를 갱신하는 과정에서
현재 노드까지 최단 경로의 길이 > 다음 노드까지 최단 경로의 길이라면 다음 노드와 현재 노드 사이에 "합리적인 이동경로"가 존재한다는 뜻이 된다. (최단 경로를 역방향으로 탐색하고 있음을 유의하자.)
이를 만족하면 점화식 dp[현재 노드] += dp[다음 노드]을 통해 최종적으로 1번 노드에서 출발하는 합리적인 이동경로의 수를 구할 수 있다.
dp 진행 예시 : 2번 노드와 1번 노드만 있고 둘이 연결되어 있다고 하자.
1. 2번 노드에서 탐색 후 1번 노드를 큐에 삽입
2. 큐에 꺼낸 1번 노드는 2번 노드와 합리적인 이동경로가 존재하므로 2번에서 출발했을 때 합리적인 이동경로의 수를 1번 노드에 합산하면 테이블을 채울 수 있다.
전체 코드
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
|
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
int n, m;
int dist[1001];
int dp[1001];
void dijkstra(graph &al);
int main()
{
fill(dist, dist + 1001, numeric_limits<int>::max());
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
graph adj(n + 1);
for (int i = 0; i < m; ++i)
{
int go, to, fee;
cin >> go >> to >> fee;
adj[go].push_back({to, fee});
adj[to].push_back({go, fee});
}
dijkstra(adj);
cout << dp[1];
}
void dijkstra(graph &al)
{
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, 2});
dist[2] = 0;
dp[2] = 1;
while (pq.size())
{
auto cur = pq.top();
pq.pop();
if (cur.first > dist[cur.second])
continue;
for (auto item: al[cur.second])
{
int ndist = item.second + cur.first;
if (ndist < dist[item.first])
{
dist[item.first] = ndist;
pq.push({ndist, item.first});
}
if (cur.first > dist[item.first])
dp[cur.second] += dp[item.first];
}
}
}
|
cs |
탐색 후 DP를 수행한 솔루션 1이 비교적 느린 결과를 보여준다.
728x90
728x90
'백준 > DP' 카테고리의 다른 글
백준 1328 - 고층 빌딩 (0) | 2020.11.15 |
---|---|
[KOI] 백준 1983 - 숫자 박스 (0) | 2020.11.15 |
백준 1750 - 서로소의 개수 (0) | 2020.11.08 |
백준 2228 - 구간 나누기 (0) | 2020.10.11 |
[KOI] 백준 2666 - 벽장문의 이동 (0) | 2020.10.09 |