HDU 1874 暢通工程續 + HDU 2544 最短路 最短路水題，dijkstra解法。

floyd解法

今天初看dijkstra，先拿這兩題練手，其他變形題還是不是很懂。

模版題，純練打字。。。

HDU 1874：

[cpp] 
#include <cstdio>  
 
#define MAXN 200  
#define INF 0xfffff   
 
int n; 
int Edge[MAXN][MAXN]; 
int s[MAXN]; 
int dist[MAXN]; 
int path[MAXN]; 
 
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 && INF > dist[i]) 
            path[i] = v0; 
        else 
            path[i] = -1; 
    } 
    s[v0] = 1; 
    dist[v0] = 0; 
    for (i = 0; i < n - 1; i++) { 
        int min = INF, u = v0; 
        for (j = 0; j < n; j++) 
            if (!s[j] && dist[j] < min){ 
                u = j; 
                min = dist[j]; 
            }//if  
        s[u] = 1; 
        for (k = 0; k < n; k++) { 
            if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) { 
                dist[k] = dist[u] + Edge[u][k]; 
                path[k] = u; 
            }//if  
        }//for  
    }//for  
} 
 
int main() { 
    int m; 
    int i, j; 
    while (scanf("%d%d", &n, &m) != EOF) { 
        for (i = 0; i < n; i++) 
            for (j = 0; j < n; j++) 
                if (i == j) 
                    Edge[i][j] = 0; 
                else 
                    Edge[i][j] = INF; 
        int x, y, z; 
        for (i = 0; i < m; i++) { 
            scanf("%d%d%d", &x, &y, &z); 
            if (z < Edge[x][y]) 
                Edge[y][x] = Edge[x][y] = z; 
        } 
        scanf("%d%d", &x, &y); 
        Dijkstra(x); 
        if (dist[y] < INF) 
            printf("%d\n", dist[y]); 
        else 
            printf("-1\n"); 
    }//while  
    return 0; 
} 

#include <cstdio>

#define MAXN 200
#define INF 0xfffff

int n;
int Edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];
int path[MAXN];

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 && INF > dist[i])
   path[i] = v0;
  else
   path[i] = -1;
 }
 s[v0] = 1;
 dist[v0] = 0;
 for (i = 0; i < n - 1; i++) {
  int min = INF, u = v0;
  for (j = 0; j < n; j++)
   if (!s[j] && dist[j] < min){
    u = j;
    min = dist[j];
   }//if
  s[u] = 1;
  for (k = 0; k < n; k++) {
   if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) {
    dist[k] = dist[u] + Edge[u][k];
    path[k] = u;
   }//if
  }//for
 }//for
}

int main() {
 int m;
 int i, j;
 while (scanf("%d%d", &n, &m) != EOF) {
  for (i = 0; i < n; i++)
   for (j = 0; j < n; j++)
    if (i == j)
     Edge[i][j] = 0;
    else
     Edge[i][j] = INF;
  int x, y, z;
  for (i = 0; i < m; i++) {
   scanf("%d%d%d", &x, &y, &z);
   if (z < Edge[x][y])
    Edge[y][x] = Edge[x][y] = z;
  }
  scanf("%d%d", &x, &y);
  Dijkstra(x);
  if (dist[y] < INF)
   printf("%d\n", dist[y]);
  else
   printf("-1\n");
 }//while
 return 0;
}

HDU 2544：

[cpp] 
#include <cstdio>  
 
#define MAXN 200  
#define INF 0xfffff   
 
int n; 
int Edge[MAXN][MAXN]; 
int s[MAXN]; 
int dist[MAXN]; 
int path[MAXN]; 
 
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 && INF > dist[i]) 
            path[i] = v0; 
        else 
            path[i] = -1; 
    } 
    s[v0] = 1; 
    dist[v0] = 0; 
    for (i = 0; i < n - 1; i++) { 
        int min = INF, u = v0; 
        for (j = 0; j < n; j++) 
            if (!s[j] && dist[j] < min){ 
                u = j; 
                min = dist[j]; 
            }//if  
        s[u] = 1; 
        for (k = 0; k < n; k++) { 
            if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) { 
                dist[k] = dist[u] + Edge[u][k]; 
                path[k] = u; 
            }//if  
        }//for  
    }//for  
} 
 
int main() { 
    int m; 
    int i, j; 
    while (scanf("%d%d", &n, &m) && n && m) { 
        for (i = 0; i < n; i++) 
            for (j = 0; j < n; j++) 
                if (i == j) 
                    Edge[i][j] = 0; 
                else 
                    Edge[i][j] = INF; 
        int x, y, z; 
        for (i = 0; i < m; i++) { 
            scanf("%d%d%d", &x, &y, &z); 
            if (z < Edge[x-1][y-1]) 
                Edge[y-1][x-1] = Edge[x-1][y-1] = z; 
        } 
        Dijkstra(0); 
        printf("%d\n", dist[n - 1]); 
    }//while  
    return 0; 
} 

#include <cstdio>

#define MAXN 200
#define INF 0xfffff

int n;
int Edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];
int path[MAXN];

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 && INF > dist[i])
   path[i] = v0;
  else
   path[i] = -1;
 }
 s[v0] = 1;
 dist[v0] = 0;
 for (i = 0; i < n - 1; i++) {
  int min = INF, u = v0;
  for (j = 0; j < n; j++)
   if (!s[j] && dist[j] < min){
    u = j;
    min = dist[j];
   }//if
  s[u] = 1;
  for (k = 0; k < n; k++) {
   if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) {
    dist[k] = dist[u] + Edge[u][k];
    path[k] = u;
   }//if
  }//for
 }//for
}

int main() {
 int m;
 int i, j;
 while (scanf("%d%d", &n, &m) && n && m) {
  for (i = 0; i < n; i++)
   for (j = 0; j < n; j++)
    if (i == j)
     Edge[i][j] = 0;
    else
     Edge[i][j] = INF;
  int x, y, z;
  for (i = 0; i < m; i++) {
   scanf("%d%d%d", &x, &y, &z);
   if (z < Edge[x-1][y-1])
    Edge[y-1][x-1] = Edge[x-1][y-1] = z;
  }
  Dijkstra(0);
  printf("%d\n", dist[n - 1]);
 }//while
 return 0;
}