#include <tuple>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges){
//그래프 및 방문 여부 초기화
for(int i=0; i<MAX_NODES; ++i){
fill_n(graph[i], MAX_NODES, INF);
visited[i] = false
}
//간선 정보 그래프로 표현
for (const auto &[from, to, weight] : edges){
graph[from][to] = weight;
}
//시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
vector<int> distances(numNodes, INF);
distances[start] = 0;
for(int i=0; i<numNodes - 1; ++i){
int minDistance = INF;
int closestNode = -1;
//최소 거리 노드 찾기
for(int j = 0; j < numNodes; ++j){
if(!visited[j] && distances[j] < mindistance) {
minDistance = distances[j];
closestNode = j;
}
}
visited[closestNode] = true;//찾은 노드 방문처리
// 인접 노드에 대한 거리 업데이트
for(int j = 0; j < numNodes; j++) {
int newDistance = distances[closestNode] + graph[closestNode][j];
if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j]){
distances[j] = newDistance;
}
}
}
return distances;
}
음의 가중치가 있는 경우에도 노드 갯수 만큼 반복을 통해 최소 비용을 찾을 수 있다는 것이 포인트, 하지만 음수 간선의 순환이 있다면 음의 무한대로 비용이 발생
#include <limits>
#include <tuple>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max();
vector<int> solution(int num_vertices, vector<tuple<int,int,int>> edges,int source){
vector<vector<pair<int,int>>> graph(num_vertices);
//간선 정보를 활용해서 인접 리스트를 생성
for (auto &edge : edges){
int from, to, weight;
tie(from, to, weight) = edge;
graph[from].emplace_back(to,weight);
}
//현재까지 구한 최소 비용을 INF로 설정 (시작 노드는 제외)
vector<int> distance(num_vertices, INF);
distance[source] = 0;
// 정점의 개수 -1만큼 최소 비용을 갱신
for(int i = 0; i < num_vertices - 1; ++i){
for(int u = 0; u<num_vertices; ++u){
for(const auto &[v, weight] : graph[u]){
if(distance[u]+weight<distance[v]){
distance[v] = distance[u] + weight;
}
}
}
}
//음의 순환이 있는 지 확인
for(int u =0 ;u<num_vertices;++u){
for(const auto &[v,weight]:graph[u]){
if(distance[u] + weight <distance[v]){
return vector<int>(1,-1);
}
}
}
return distance;
}