单源最短路（Bellman_Ford)
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define INF 0x7fffffffusing namespace std;const int maxn = 1000;const int maxm = 1000000;typedef struct node{ int w; int to; int next;}NODE;int dist[maxn];NODE edge[maxm];int head[maxn];int num = 0;int s = 0;int n, m;int Bellman_Ford(){ int i, j, k; for(i = 0; i < n; i++){ dist[i] = INF; } dist[s] = 0;//别忘了给S赋值这可是程序执行的开始。 for(i= 0; i < n-1; i++){ for(j = 0; j < n; j++){ if(dist[j] == INF) { continue; } for(k = head[j]; k != -1; k = edge[k].next){ if(edge[k].w != INF && dist[edge[k].to] > dist[j] + edge[k].w){ dist[edge[k].to] = dist[j] + edge[k].w; } } } } for(j = 0; j < n; j++){ if(dist[j] == INF){ continue; } for(k = head[j]; k != -1; k = edge[k].next){ if(edge[k].w !=INF && dist[edge[k].to] > dist[j] + edge[k].w){ return false; } } } return true;}void output_result(){ for(int i = 1; i <= n; i++){ printf("%d\n", dist[i]); }}void init(){ num = 0; memset(dist, 0, sizeof(dist)); memset(head, -1, sizeof(head));}int main(){ int a = 0, b = 0, c = 0; while(scanf("%d%d", &n, &m)!=EOF){ init(); a = INF; cout << a << endl; for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &c); edge[num].w = c; edge[num].to = b; edge[num].next = head[a]; head[a] = num; num++; } cout << "please input a source:" << endl; scanf("%d", &s); int res = Bellman_Ford(); if(res) { output_result(); } } return 0;}/****************测试数据算法导论P3625 101 2 61 3 72 3 82 4 52 5 -43 4 -33 5 94 2 -25 4 75 1 2************/