Dijkstra算法示例程序_1

好几天不写程序的结果就是以前的东西都忘得差不多了……o(╯□╰)o

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 20;
int S[MAX], dist[MAX], path[MAX], edge[MAX][MAX];
int n;
void Dijkstra(int v0) {
  int i, j, k;
  for (i = 0; i <n ; ++i) {
    dist[i] = edge[v0][i]; S[i] = 0;
    if (i != v0 && edge[v0][i] != MAXN) path[i] = v0;
    else path[i] = -1;
  }
  S[v0] = 1; dist[v0] = 0;
  for (i = 0; i < n - 1; ++i) {
    int Min = MAXN, u = v0;
    for (j = 0; j < n; ++j) {
      if (dist[j] < Min && S[j] == 0) {
        Min = dist[j]; u = j;
      }
    }
    S[u] = 1;
    for (j = 0; j < n; ++j) {
      if (S[j] == 0 && edge[u][j] != MAXN) {
        int tmp = edge[u][j] + dist[u];
        if (tmp < dist[j]) {
          dist[j] = tmp; path[j] = u;
        }
      }
    }
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("dijkstra.in", "r", stdin);
#endif
  scanf("%d", &n);
  int u, v, w, i, j, k;
  memset(edge, 0, sizeof(edge));
  while (1) {
    scanf("%d%d%d", &u, &v, &w);
    if (u == -1 && v == -1 && w == -1) break;
    edge[u][v] = w;
  }
  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; ++j) {
      if (i == j) edge[i][j] = 0;
      else if (edge[i][j] == 0) edge[i][j] = MAXN;
    }
  }
  Dijkstra(0);
  for (i = 1; i < n; ++i) {
    printf("%d\t", dist[i]);
    int Shortest[MAX]; k = 0;
    Shortest[k] = i; int po = path[i];
    while (po != -1) {
      Shortest[++k] = po; po = path[po];
    }
    for (j = k; j > 0; --j) {
      printf("%d->", Shortest[j]);
    }
    printf("%d\n", Shortest[0]);
  }

  return 0;
}

这次遇到的问题就是edge的初始化位置写错了，调好久。。