[Accept] 10099 - The Tourist Guide

This code is also another co-worker's source.
He makes it even if he didn't use any algorithm.
He made his own way that he delete the edge which is not the answer

----------------------------------------------------------------------------------------------

#include

#define MAXV            100
#define MAXDEGREE       100

typedef struct {
        unsigned int edges[MAXV+1][MAXV+1];
        unsigned int nverticies;
        unsigned int nedges;
} graph;

graph g;

typedef struct {
        unsigned int x;
        unsigned int y;
        unsigned int value;
} minSt;

minSt minList[10000];
unsigned int minCnt;

int map[100];
int cnt;

void init_graph()
{
        memset(&g, 0, sizeof(graph));
}

void set_edges(int i)
{
        g.nedges = i;
}

void set_verticies(int i)
{
        g.nverticies = i;
}

void set_edge(int x, int y,int weight)
{
        g.edges[x][y] = weight;
        g.edges[y][x] = weight;

        minList[minCnt].x = x;
        minList[minCnt].y = y;
        minList[minCnt++].value = weight;
}

void sort_min()
{
        minSt tmp;
        int i,j;

        for ( i = 0 ; i < minCnt ; i++ ) {
                for ( j = i ; j < minCnt ; j++ ) {
                        if ( minList[i].value > minList[j].value ) {
                                tmp = minList[i];
                                minList[i] = minList[j];
                                minList[j] = tmp;
                        }
                }
        }
#if 0
        for ( i = 0 ; i < minCnt ; i++ ) {
                printf("x(%d) y(%d) weight(%d)\n",minList[i].x, minList[i].y, minList[i].value);
        }
#endif
}

void print_graph()
{
        int i,j;
        printf("==========================\n");
        for ( i = 1 ; i <= g.nverticies ; i++ ) {
                for ( j = 1 ; j <= g.nverticies ; j++ ) {
                        printf("%3d ",g.edges[i][j]);
                }
                printf("\n");
        }
}

unsigned int ConnMap[101][101];

int isConnected2()
{
        int i,j,k;

        memcpy(ConnMap, g.edges, sizeof(ConnMap));

        for ( i = 1 ; i <= g.nverticies ; i++ ) {
                for ( j = 1 ; j <= g.nverticies ; j++ ) {
                        if ( i == j )
                                continue;
                        for ( k = 1 ; k <= g.nverticies ; k++ ) {
                                if ( j == k )
                                        continue;
                                if ( i == k )
                                        continue;
                                if ( ConnMap[i][j] > 0 && ConnMap[j][k] > 0 ) {
                                        ConnMap[i][j] = 1;
                                        ConnMap[j][i] = 1;

                                        ConnMap[j][k] = 1;
                                        ConnMap[k][j] = 1;

                                        ConnMap[i][k] = 1;
                                        ConnMap[k][i] = 1;
                                }
                        }
                }
        }

#if 0
        printf("==========================\n");
        for ( i = 1 ; i <= g.nverticies ; i++ ) {
                for ( j = 1 ; j <= g.nverticies ; j++ ) {
                        printf("%3d ",ConnMap[i][j]);
                }
                printf("\n");
        }
        exit(0);
#endif

}

int isConnected(int start,int end)
{
        register unsigned int i,j;
        register unsigned int check=0;

        if ( start == end )
                return 1;

#if 1
        if ( g.edges[start][end] > 0 ) {
                return 1;
        }
#endif

        for ( i = 1 ; i <= g.nverticies ; i++ ) {
                if ( i == start )
                        continue;

                check = 0;
                for ( j = 0 ; j < cnt ; j++ ) {
                        if ( map[j] == i ) {
                                check=1;
                                break;
                        }
                }
                if ( check == 1 )
                        continue;

                if ( g.edges[start][i] > 0) {
                        map[cnt]=start;
                        cnt++;
                        if (isConnected(i,end) == 1 ) {
                                return 1;
                        }
                }
        }
        return 0;
}


void del_edge(int x,int y)
{
        g.edges[x][y] = 0;
        g.edges[y][x] = 0;
}

int main()
{
        int edge;
        int vert;
        int x,y;
        int i,weight;
        int start, end, people;
        int min;
        int scenario=1;

        while(1) {
                init_graph();
                scanf("%d %d",&vert,&edge);
                if ( vert == 0 )
                        break;
                if ( vert < 1 || vert > 100 )
                        continue;

                set_verticies(vert);
                set_edges(edge);

                for ( i = 0 ; i < edge ; i++ ) {
                        scanf("%d %d %d",&x,&y,&weight);
                        set_edge(x,y,weight);
                }
                scanf("%d %d %d",&start,&end,&people);

                sort_min();

                cnt = 0;
                i = 0;

                while ( isConnected(start,end)) {
#if 0
                while ( 1 ) {
                        isConnected2();
                        if ( ConnMap[start][end] == 0 )
                                break;
#endif

                        cnt = 0;
                        min = minList[i].value;
                        del_edge(minList[i].x,minList[i].y);
                        i++;
                }

                if ( people % (min-1 ) == 0 )
                        min = people/(min-1);
                else
                        min = people/(min-1) + 1;

                printf("Scenario #%d\n",scenario++);
                printf("Minimum Number of Trips = %d\n\n",min);

                minCnt = 0;

                fflush(stdin);
        }

        return 0;
}


#if 0
int find_min(int *x, int *y)
{
        int i,j;
        int min=99999;
        int a;

        for ( i = 1 ; i <= g.nverticies ; i++ ) {
                for ( j = 1 ; j <= g.nverticies ; j++ ) {
                        if ( g.edges[i][j] > 0 && g.edges[i][j] < min ){
                                min = g.edges[i][j];
                                *x = i;
                                *y = j;
                        }
                }
        }
        return min;
}
#endif