BOJ : https://www.acmicpc.net/problem/1504

github : https://github.com/junho0956/Algorithm/blob/master/1504/1504/%EC%86%8C%EC%8A%A4.cpp

 

확인해야할 경우는 2가지 입니다.

s -> v1 -> v2 -> e

s -> v2 -> v1 -> e

이 둘중 최솟값을 고르면 됩니다.

이 때 WA를 받게된 사소한 부분이 있는데

INF를 987654321로 두고 문제를 풀 때

한 경로 당 최대 3번까지 INF를 더하게 될 수도 있습니다.

이 때 int 의 범위를 벗어나므로 INF 값을 좀더 작은 값으로 사용해주시거나 (ex:800*1000 이상)

답 받을때만 long long 을 사용해주시면 됩니다.

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
typedef pair<int, int> pii;
#define INF 987654321
 
bool visit[802];
vector<pii> v[802];
priority_queue<pii, vector<pii>, greater<pii> > q;
int N, E, ms, me;
 
vector<int> dijkstra(int start) {
    memset(visit, 0, sizeof(visit));
    vector<int> dist(N+1, INF);
    dist[start] = 0;
    q.push({ 0,start });
 
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
        
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ dist[vertex], vertex });
            }
        }
    }
 
    return dist;
}
 
void solve() {
    cin >> N >> E;
    for (int i = 0; i < E; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
        v[e].push_back({ s,w });
    }
    cin >> ms >> me;
 
    vector<int> dist;
 
    long long ans1, ans2;
    dist = dijkstra(1);
    ans1 = dist[ms];
    ans2 = dist[me];
 
    dist = dijkstra(ms);
    ans1 += dist[me];
    ans2 += dist[N];
 
    dist = dijkstra(me);
    ans1 += dist[N];
    ans2 += dist[ms];
 
    long long ans = min(ans1, ans2);
    if (ans >= INF) cout << "-1";
    else cout << ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1026번 보물  (0) 2020.02.28
BOJ 2240번 자두나무  (0) 2020.02.26
BOJ 1238 파티  (0) 2020.02.23
BOJ 1916번 최소비용 구하기  (0) 2020.02.23
BOJ 1753번 최단경로  (0) 2020.02.23

BOJ : https://www.acmicpc.net/problem/1238

github : https://github.com/junho0956/Algorithm/blob/master/1238/1238/%EC%86%8C%EC%8A%A4.cpp

 

정점의 크기가 최대 1000이기 때문에

dist[i]+dist[X] 를 정점 i에서 X로 + 정점 X에서 정점 i로 가는 이동거리라고 생각했을 때

시간복잡도가 nlogn * n => n^2logn 이여도 시간내로 해결가능합니다!

 

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 <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef pair<int, int> pii;
 
int N, M, X;
bool visit[1001];
vector<pii> v[1001];
priority_queue<pii, vector<pii>, greater<pii> > q;
 
vector<int> dijkstra(int start) {
    vector<int> dist(N+1,INF);
    for (int i = 1; i <= N; i++)visit[i] = false;
    dist[start] = 0;
 
    q.push({ 0,start });
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
 
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ dist[vertex], vertex });
            }
        }
    }
 
    return dist;
}
 
void solve() {
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
    vector<int> dist = dijkstra(X);
 
    int ans = -1;
    for (int i = 1; i <= N; i++) {
        if (i == X) continue;
        vector<int> dist2 = dijkstra(i);
 
        if (dist2[X] >= INF) continue;
        ans = max(ans, dist[i] + dist2[X]);
    }
 
    cout << ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2240번 자두나무  (0) 2020.02.26
BOJ 1504번 특정한 최단 경로  (0) 2020.02.24
BOJ 1916번 최소비용 구하기  (0) 2020.02.23
BOJ 1753번 최단경로  (0) 2020.02.23
BOJ 2294번 동전 2  (0) 2020.02.21

BOJ : https://www.acmicpc.net/problem/1916

github : https://github.com/junho0956/Algorithm/blob/master/1916/1916/%EC%86%8C%EC%8A%A4.cpp

 

임의의 출발점에서 원하는 정류장까지의 각 최단거리를 구하려면

다익스트라의 개념을 활용해야합니다.

우선순위 큐를 이용하여 nlogn 에 구현하였습니다

 

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
#define INF 987654321
 
bool visit[1001];
int dist[1001];
int N, M;
priority_queue<pii, vector<pii>, greater<pii> > q;
vector<pii> v[1001];
 
void dijkstra(int start, int finish) {
    dist[start] = 0;
    q.push({ 0,start });
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
 
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ len + distance, vertex });
            }
        }
    }
}
 
void solve() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) dist[i] = INF;
    for (int i = 0; i < M; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
    int s, e; cin >> s >> e;
    dijkstra(s, e);
    cout << dist[e];
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1504번 특정한 최단 경로  (0) 2020.02.24
BOJ 1238 파티  (0) 2020.02.23
BOJ 1753번 최단경로  (0) 2020.02.23
BOJ 2294번 동전 2  (0) 2020.02.21
BOJ 10835번 카드게임  (0) 2020.02.21

BOJ : https://www.acmicpc.net/problem/1753

github : https://github.com/junho0956/Algorithm/blob/master/1753/1753/%EC%86%8C%EC%8A%A4.cpp

 

한 정점에서 다른 모든 정점으로의 최단거리를 구하려면

다익스트라의 개념을 활용해야 합니다.

일반적으로 구현하면N^2의 복잡도가 필요하기 때문에 우선순위 큐를 사용하여 NlogN 에 구현하였습니다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
typedef pair<int, int> pii;
 
int vertex, edge;
vector<pii> v[20001];
priority_queue<pii, vector<pii>, greater<pii> > q;
int dist[20001];
bool visit[20001];
 
void dijkstra(int start) {
    for (int i = 1; i <= vertex; i++) dist[i] = INF;
    dist[start] = 0;
    q.push({ 0,start });
 
    while (!q.empty()) {
        int w = q.top().first;
        int node = q.top().second;
        q.pop();
 
        if (visit[node]) continue;
        visit[node] = true;
 
        for (int i = 0; i < v[node].size(); i++) {
            int cur = v[node][i].first;
            int weight = v[node][i].second;
            if (!visit[cur] && dist[cur] > w + weight) {
                dist[cur] = w + weight;
                q.push({ w + weight, cur });
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    int start_vertex;
    cin >> vertex >> edge >> start_vertex;
    for (int i = 0; i < edge; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
 
    dijkstra(start_vertex);
 
    for (int i = 1; i <= vertex; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1238 파티  (0) 2020.02.23
BOJ 1916번 최소비용 구하기  (0) 2020.02.23
BOJ 2294번 동전 2  (0) 2020.02.21
BOJ 10835번 카드게임  (0) 2020.02.21
BOJ 10995번 별 찍기 - 20  (0) 2020.02.21

+ Recent posts

티스토리툴바