taxiuri

#include <bits/stdc++.h>

using namespace std;

ifstream fin("taxiuri.in");
ofstream fout("taxiuri.out");

const int NMAX = 301;
const int oo = (1<<30);

int n, m, q;

vector < vector < int > > mat(NMAX, vector< int >(NMAX));

void Read()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, t;
        fin >> x >> y >> t;
        mat[x][y] = mat[y][x] = t;
    }
}

int st[NMAX];

void init(int k)
{
    st[k] = 0;
}

int succesor(int k)
{
    if(st[k] < n)
    {
        st[k]++;
        return 1;
    }
    else
        return 0;
}

bool valid(int k)
{
    if(k > 1)
    {
        if(mat[st[k]][st[k-1]] == 0)
            return 0;
        for(int i=1; i<k; i++)
            if(st[k] == st[i])
                return 0;
        return 1;
    }
    return 0;
}

int solutie(int k, int y)
{
    return st[k] == y;
}

void tipar(int k, int v[], int &minn, int &p)
{
    int s = 0;
    for(int i=1; i<=k; i++)
        s += mat[st[i]][st[i-1]];
    if(s < minn)
    {
        minn = s;
        for(int i=1; i<=k; i++)
            v[i] = st[i];
        p = k;
    }
}

void bkt(int k, int y, int v[], int &minn, int &p)
{
    init(k);
    while(succesor(k))
        if(valid(k))
            if(solutie(k,y))
                tipar(k,v, minn, p);
            else
                bkt(k+1,y, v, minn, p);
}

void Write()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
}

int main()
{
    clock_t tStart = clock();
    Read();
    int v[100] = {0};
    fin>>q;
    for(int i=1; i<=q; i++)
    {
        int p;
        int minn = oo;
        int x=5, y=2;
        fin >> x >> y;
        st[1] = x;
        for(int j=1; j<=p; j++)
            v[i] = 0;
        bkt(2, y ,v ,minn, p);
        for(int j=1; j<=p; j++)
            fout << v[j] << " ";
        fout<<endl;
    }

    cout<<(float)(clock()-tStart)/CLOCKS_PER_SEC;
    return 0;
}