https://www.acmicpc.net/problem/11657
λ¬Έμ
Nκ°μ λμκ° μλ€. κ·Έλ¦¬κ³ ν λμμμ μΆλ°νμ¬ λ€λ₯Έ λμμ λμ°©νλ λ²μ€κ° Mκ° μλ€. κ° λ²μ€λ A, B, Cλ‘ λνλΌ μ μλλ°, Aλ μμλμ, Bλ λμ°©λμ, Cλ λ²μ€λ₯Ό νκ³ μ΄λνλλ° κ±Έλ¦¬λ μκ°μ΄λ€. μκ° Cκ° μμκ° μλ κ²½μ°κ° μλ€. C = 0μΈ κ²½μ°λ μκ° μ΄λμ νλ κ²½μ°, C < 0μΈ κ²½μ°λ νμλ¨Έμ μΌλ‘ μκ°μ λλμκ°λ κ²½μ°μ΄λ€.
1λ² λμμμ μΆλ°ν΄μ λλ¨Έμ§ λμλ‘ κ°λ κ°μ₯ λΉ λ₯Έ μκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
λ΄ μ½λ
벨λ§ν¬λ μ΅λ¨ 거리 μκ³ λ¦¬μ¦μ 곡λΆνκ³ μμ λ₯Ό νμ΄λ΄€λ€.
μ°Έκ³ λ‘ costsλ₯Ό long longμΌλ‘ λμ΄μΌνλ μ΄μ λ λ²μ€ λ Έμ μ μ΅λ κ°μ 500 -1 * κ°μ μ κ°μ 6,000λ² μ°μ°μ μ§ννλ λ°λ€κ° μ΅λ κ°μ λΉμ© μ λκ°μ΄ 10,000μ΄κΈ° λλ¬Έμ μ΅λ λΉμ©μ΄ μμ² μ»€μ§ μ μκΈ° λλ¬Έμ΄λ€. κ°μ μ΄μ λ‘ MAX κ°μ μΆ©λΆν ν¬κ² λμ§ μλλ€λ©΄ λ¬Έμ κ° μκΈΈ μ μλ€.
#include <vector>
#include <iostream>
#include <algorithm>
#define MAX 9'999'999
using namespace std;
struct Edge
{
int from = 0;
int to = 0;
int cost = MAX;
};
int main()
{
int start = 1;
int node, edge;
cin >> node >> edge;
vector<Edge> edges(edge);
vector<long long> costs(node + 1, MAX);
// μκΈ° μμ μΌλ‘ κ°λ λΉμ©μ 0
costs[start] = 0;
// κ°μ μ
λ ₯
for (int i = 0; i < edge; ++i)
{
int a, b, v;
cin >> a >> b >> v;
edges[i].from = a;
edges[i].to = b;
edges[i].cost = v;
}
// 벨λ§ν¬λ
// 1. n-1λ² κ°μ λ§λ€ μ΅μ λΉμ©μ ꡬνλ€
for (int n = 1; n < node; ++n)
{
for (int e = 0; e < edge; ++e)
{
// κ°μ μ μμ μ§μ μ΄ start λ
Έλμ μ°κ²°λμ΄ μμ§ μλ€λ©΄ continue;
if (costs[edges[e].from] == MAX)
continue;
// νμ¬ κ°μ μ κ±°μ³ κ°λ κ²μ΄ λ λΉ λ₯΄λ€λ©΄ κ°±μ
costs[edges[e].to] = min(costs[edges[e].to], costs[edges[e].from] + edges[e].cost);
}
}
// 2. νλ² λ κ°±μ μ μλ. λ§μ½ κ°±μ λλ€λ©΄ μμ κ°μ μνμ΄ λ°μν κ²μ΄λ―λ‘ -1μ μΆλ ₯
for (int e = 0; e < edge; ++e)
{
// κ°μ μ μμ μ§μ μ΄ start λ
Έλμ μ°κ²°λμ΄ μμ§ μλ€λ©΄ continue;
if (costs[edges[e].from] == MAX)
continue;
// νμ¬ κ°μ μ κ±°μ³ κ°λ κ²μ΄ λ λΉ λ₯΄λ€λ©΄ κ°±μ
if (costs[edges[e].to] > costs[edges[e].from] + edges[e].cost)
{
cout << -1 << endl;
return 0;
}
}
// κ²°κ³Ό μΆλ ₯
for (int n = 2; n <= node; ++n)
{
if (costs[n] == MAX) cout << -1 << endl;
else cout << costs[n] << endl;
}
return 0;
}
'π₯οΈ Study Note > Coding Test' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[νλ‘κ·Έλλ¨Έμ€]level.3 - μκ³Ό λλ (C++) (0) | 2023.09.14 |
---|---|
[νλ‘κ·Έλλ¨Έμ€]level.3 - λ―Έλ‘ νμΆ λͺ λ Ήμ΄ (C++) (0) | 2023.09.07 |
[νλ‘κ·Έλλ¨Έμ€]level.3 - μμ (C++) (0) | 2023.09.05 |
[νλ‘κ·Έλλ¨Έμ€]level.3 - ν©μΉ νμ μκΈ (C++) (0) | 2023.09.05 |
[νλ‘κ·Έλλ¨Έμ€]level.2 - μ΄λͺ¨ν°μ½ ν μΈ νμ¬(C++) (1) | 2023.08.28 |