样例输入：

7

0 1 6

0 2 5

0 3 5

1 4 -1

2 1 -2

2 4 1

3 2 -2

3 5 -1

4 6 3

5 6 3

-1 -1 -1

样例输出

1 0→3→2→1

3 0→3→2

5 0→3

0 0→3→2→1→4

4 0→3→5

3 0→3→2→1→4→6

 

 

#include 
     
      #include 
      
       #define INF    1000000    //无穷大#define MAXN 20        //顶点个数最大值int n;        //顶点个数int Edge[MAXN][MAXN];    //邻接矩阵int dist[MAXN];    //int path[MAXN];    //void Bellman( int v0 )    //求顶点v0到其他顶点的最短路径{    int i, j, k, u;        //循环变量    for( i=0; i
       
        0; j-- )            printf( "%d→", shortest[j] );        printf( "%d\n", shortest[0] );    }    return 0;}
       
      
     

 用vertor实现Bellman:

#include
     
      #include
      
       using namespace std;const int N = 100;const int INF = 0x3f3f3f3f;struct Edge{   //用于记录一组关系    int u,v,w;};vector
       
         edge;  //用于保存图的关系int dis[N];      //源点到各点的最短距离int path[N];     //源点到各点的路径int road[N];     //用于逆向追中输出路径void init(){    while(!edge.empty()){        edge.clear();    }}void Bellman_Ford_vector(int v,int n,int m){   //源点,定点数，边数    int i,j;    memset(path,255,sizeof(path));   //初始化路径为-1;    for(i=0;i<=n;i++){               //初始化dis[i]为不可到达        dis[i] = INF;    }    dis[v] = 0;      //把源点到自己的路径改为0    for(i=0;i
        
         的引入能否缩短源点到v的距离            if(dis[edge[j].u] + edge[j].w < dis[edge[j].v]){ //若可以松弛，更新                 dis[edge[j].v] = dis[edge[j].u] + edge[j].w;                 path[edge[j].v] = edge[j].u;            }        }    }}int main(){    freopen("in.txt","r",stdin);    int n;    Edge temp;    while(scanf("%d",&n)!=EOF){        init();        while(scanf("%d%d%d",&temp.u,&temp.v,&temp.w) && ~temp.u && ~temp.v && ~temp.w){            edge.push_back(temp);  //把关系添加到vector        }        Bellman_Ford_vector(0,n,edge.size());        for(int i=1;i
         
          ",road[k--]);            }            printf("%d\n",road[k]);        }    }    return 0;}