#include <stdio.h>
#include <iostream>
#include <string>
#include  <string.h>
#include <stdlib.h>
using namespace std;
#define INF 10000000
int start;
int over;
bool sign[9];
int NUM;
int path[9][9];
int road[9];
void input()
	{
	   path[0][0] = INF;	path[0][1] = INF;	path[0][2] = 10;	path[0][3] = INF;	path[0][4] = 30;	path[0][5] = 100;	path[0][6] = INF;	path[0][7] = INF;	path[0][8] = INF;
			path[1][0] = INF;	path[1][1] = INF;	path[1][2] = 5;		path[1][3] = INF;	path[1][4] = INF;	path[1][5] = INF;	path[1][6] = INF;	path[1][7] = INF;	path[1][8] = INF;
			path[2][0] = INF;	path[2][1] = INF;	path[2][2] = INF;	path[2][3] = 50;	path[2][4] = INF;	path[2][5] = INF;	path[2][6] = INF;	path[2][7] = INF;	path[2][8] = INF;
			path[3][0] = INF;	path[3][1] = INF;	path[3][2] = INF;	path[3][3] = INF;	path[3][4] = INF;	path[3][5] = 10;	path[3][6] = INF;	path[3][7] = INF;	path[3][8] = INF;
			path[4][0] = INF;	path[4][1] = INF;	path[4][2] = INF;	path[4][3] = 20;	path[4][4] = INF;	path[4][5] = 60;	path[4][6] = INF;	path[4][7] = INF;	path[4][8] = INF;
			path[5][0] = INF;	path[5][1] = INF;	path[5][2] = INF;	path[5][3] = INF;	path[5][4] = INF;	path[5][5] = INF;	path[5][6] = INF;	path[5][7] = INF;	path[5][8] = INF;
			path[6][0] = INF;	path[6][1] = INF;	path[6][2] = INF;	path[6][3] = INF;	path[6][4] = INF;	path[6][5] = INF;	path[6][6] = INF;	path[6][7] = INF;	path[6][8] = INF;
			path[7][0] = INF;	path[7][1] = INF;	path[7][2] = INF;	path[7][3] = INF;	path[7][4] = INF;	path[7][5] = INF;	path[7][6] = INF;	path[7][7] = INF;	path[7][8] = INF;
			path[8][0] = INF;	path[8][1] = INF;	path[8][2] = INF;	path[8][3] = INF;	path[8][4] = INF;	path[8][5] = INF;	path[8][6] = INF;	path[8][7] = INF;	path[8][8] = INF;
	}
void init()
{
    memset(road, 0, sizeof(road));
    NUM = 9;
    for(int i=0; i<NUM; i++)
        sign[i] =false;
    input();
}
void findRoad(int road[], int length)
{
    for(int i=0; i<length; i++)
        cout << " " << road[i];
    cout << over << endl;
}
void dfs(int tp, int road[], int length)
{
    sign[tp] = true;
    for(int i=0; i<NUM; i++)
    {
        if(path[tp][i] != INF && sign[i] != true)
        {
            if(tp == over)
            {
                //road[length++] =  over;
                findRoad(road, length);
            }
        else
            {
                road[length++] = tp;
               //  for(int i=0; i<6; i++)
                dfs(i, road, length);
                    sign[i] = false;
               length--;
            }
        }
    }
}
int main()
{
    init();
    //freopen("read.txt", "r", stdin);
    start = 0; over = 3;
    dfs(start, road, 0);
    cout <<  "ok" << endl;
}

附件列表