Dijkstra's algorithm

# Shortest Path in a Weighted Directed Graph

| | |
| :--- | :--- |
| **Input** | Standard input |
| **Output** | Standard output |

### Problem Statement
Given a directed weighted graph, find the shortest distance from a specified starting vertex $S$ to a target vertex $F$.

### Input Format
- The first line contains four integers: $N, M, S,$ and $F$ ($1 \le N \le 100, 1 \le M \le 10,000, 1 \le S, F \le N$), where $N$ is the number of vertices, $M$ is the number of edges, $S$ is the starting vertex, and $F$ is the destination.
- Each of the following $M$ lines contains three integers representing an edge: the starting vertex, the ending vertex, and the cost of the edge (weight $\le 100$).

### Output Format
Print the shortest distance to the target vertex. If no path exists between the vertices, print `-1`.

### Examples
| Input | Output |
| :--- | :--- |
| `3 6 2 1` <br> `1 2 1` <br> `1 3 1` <br> `2 1 4` <br> `2 3 1` <br> `3 1 2` <br> `3 2 1` | `3` |

#include <iostream>
using namespace std;

const int MAXN = 101;
const int INF = 1000000000;

int main() {
    int N, M, S, F;
    cin >> N >> M >> S >> F;
    
    int graph[MAXN][MAXN];
    int dist[MAXN];
    bool visited[MAXN];
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            graph[i][j] = INF;
        }
        graph[i][i] = 0;
    }
    
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        if (w < graph[a][b]) {
            graph[a][b] = w;
        }
    }
    
    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[S] = 0;
    
    for (int i = 1; i <= N; i++) {
        int min_v = -1;
        int min_d = INF;
        for (int j = 1; j <= N; j++) {
            if (!visited[j] && dist[j] < min_d) {
                min_d = dist[j];
                min_v = j;
            }
        }
        
        if (min_v == -1 || min_d == INF) {
            break;
        }
        
        visited[min_v] = true;
        
        for (int j = 1; j <= N; j++) {
            if (graph[min_v][j] < INF && dist[j] > dist[min_v] + graph[min_v][j]) {
                dist[j] = dist[min_v] + graph[min_v][j];
            }
        }
    }
    
    if (dist[F] >= INF) {
        cout << -1 << endl;
    } else {
        cout << dist[F] << endl;
    }
    
    return 0;
}