최소비용 구하기

/* 가중치 그래프 최단경로 Dijkstra 알고리즘 - 음수가 아닌 가중치를 가진 단순 그래프 G에서 임의의 정점 u0(다익스트라 출발점)로부터 다른 모든 정점으로의 최단경로를 찾는 알고리즘 */ #include <stdio.h> #define INF 987654321; int V, E; int start, end; int map[1002][1002]; int dist[1002]; int isVisited[1002]; void input() { scanf("%d %d", &V, &E); for (int i = 1; i <= V; i++) { for (int j = 1; j <= V; j++) { map[i][j] = INF; } dist[i] = INF; isVisited[i] = 0; } for (int i = 1; i <= E; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); if (map[u][v] > w) map[u][v] = w; } scanf("%d", &start); scanf("%d", &end); } void dijkstra() { int min; int v = 0; dist[start] = 0; for (int i = 1; i <= V; i++) { min = INF; for (int j = 1; j <= V; j++) { if (isVisited[j] == 0 && min > dist[j]) { min = dist[j]; v = j; } } isVisited[v] = 1; for (int j = 1; j <= V; j++) { if (dist[j]>dist[v] + map[v][j] && map[v][j] != min) { dist[j] = dist[v] + map[v][j]; } } } printf("\n"); for (int i = 1; i <= V; i++) { for (int j = 1; j <= V; j++) { printf("%d             ", map[i][j]); } printf("\n"); } } int main() { input(); dijkstra(); printf("%d", dist[end]); return 0; }