Naive Dijkstra Algorithm (适用于Dense Graph == 边的数量远远大于顶点Vertex数量),

#include <iostream>
#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;
const int N = 510;
int g[N][N], dist[N], visited[N], n, m, u, v, w;

int dijkstra(int s) {

  dist[s] = 0;
  for (int i = 0; i < n; ++i) {
    // step1:
    int min_dist = INF, t = -1;
    for (int j = 1; j <= n; ++j)
      if (!visited[j] && dist[j] < min_dist) {
        min_dist = dist[j];
        t = j;
      }

    // step2:
    visited[t] = 1;

    // step3 进行松驰操作
    for (int j = 1; j <= n; ++j)
      if (dist[t] + g[t][j] < dist[j])
        dist[j] = dist[t] + g[t][j]; 
  }

  return dist[n] == INF ? -1 : dist[n];
}

int main(void) {
  // initialize
  memset(g,    0x3f, sizeof g);
  memset(dist, 0x3f, sizeof dist);

  scanf("%d %d", &n, &m);
  while (m--) {
    scanf("%d %d %d", &u, &v, &w);
    if (w < g[u][v]) g[u][v] = w;
  }

  return printf("%d\n", dijkstra(1)), 0;
}