721 - Invitation Cards

[..]

I use heap + Dijkstra to solve the problem,
but I don't know why I got WA.
Can anyone tell me if there is any tricky case in the input?? or provide some sample input to me??
Thanks a lot!!!!!!!!!!!!!!!!!!!!!!!

[Rossi]

me too... can anybody give some test cases??

[..]

I got accepted by fixing a bug in my heap implementation.
Btw, do you handle any self loop or multiple edges in input?

[Sanghack]

I read the problem and now I think what I should do.

I found that

All the ACM student members leave the CCS each morning
At the end of the day, all students travel back to CCS

Then, can I believe that the maximum path for go to bus stop and back to CCS is less or equal than 23. (even morning is 0:00 and end of the day is 24:00)

I wanna know 'DOES IT MATTER?'

[..]

Don't think too compilcate.
In this problem no need to consider time.

[ThanhNhan]

I lost 20 submissions for this problem and coded it twice. I use priority_queue dijkstra, but keep getting WA.

Could you guys post some input for me to check ? Thank you,

Even using scanf it took like 1.7s to just read inputs, how do people get accepted in 0.5s ?

[ThanhNhan]

http://acm.pku.edu.cn/JudgeOnline/showp ... em_id=1511
This is the same problem, but I got accepted there.

This is really annoying !!!

[ThanhNhan]

Got Accepted !!!!

[lghmf]

I solved this problem by using HEAP-dijkstra, but i got MLE

how did you save memory??

Here is my source code..

#pragma warning (disable: 4786)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <list>
#include <set>
using namespace std;
#define MAX 1999999999

typedef pair<int,int> pi;
typedef vector<pi> vp;

void dijkstra(int st,vp *adj);
int v;
int d[1000001];
int ii,tet,rc;

vector<pi> adj[1000001];
vector<pi> adj1[1000001];


int main(void)
{

int i;
scanf("%d",&tet);

for(ii=1;ii<=tet;ii++)
{
scanf("%d %d",&v,&rc);

v++;

for(i=1;i<=v;i++)
{
adj.clear();
adj1.clear();
}


for(i=0;i<rc;i++)
{
int t1,t2,t3;
scanf("%d %d %d",&t1,&t2,&t3);
adj[t1].push_back(make_pair(t2,t3));
adj1[t2].push_back(make_pair(t1,t3));
}


int sol=0;

dijkstra(1,adj);

for(i=2;i<v;i++)
sol+=d;

dijkstra(1,adj1);

for(i=2;i<v;i++)
sol+=d;


cout << sol << endl;

}
return 0;
}

void dijkstra(int st,vp *adj)
{
int cost,i,t,u;
priority_queue<pi, vector<pi>, greater<pi> > que;

for(i = 1; i <= v; i++) d = MAX;
d[st] = 0;
que.push(make_pair(0, st));

while(!que.empty())
{
cost = que.top().first, u = que.top().second;
que.pop();

if(d < cost) continue;

for(i = 0; i < adj.size(); i++)
{
t = adj.first;
if(d[t] > cost + adj.second)
{
d[t] = cost + adj.second;
que.push(make_pair(d[t], t));
}
}
}
}

[sds1100]

i use heap + Dijkstra
and i use
array
int check[1000001],min,dis[1000001],from[1000001],idx;
int check2[1000001],min2,dis2[1000001],from2[1000001];
int x,y,z,a[3][1000001],b[1000001],cnt,sum=0,alln,n,m;
.. got MLE..
i use there size /2 : 500000
and i got TLE..
why??

[mars kaseijin]

Greetings sds1100,
wanna supply me with some sample inputs?
I have implemented travelling salesman algorithm + graph to solve it.

[sds1100]

hey. this is my code. ..
T-T help me

Code: Select all

#include <fstream.h>
long long int check[1000001],min,dis[1000001],idx;
long long int check2[1000001],min2,dis2[1000001];
long long int x,y,z,a[3][1000001],b[1000001],cnt,sum=0,alln,n,m;
long long int a2[3][1000001],b2[1000001];
void index(){
	int now=b[idx];
	while (now != -1) {
		if(min+a[2][now]<dis[a[0][now]] && check[a[0][now]]==0) dis[a[0][now]]=min+a[2][now];
		now=a[1][now];
	}
}
void index2(){
	int now=b2[idx];
	while (now != -1) {
		if(min+a2[2][now]<dis2[a2[0][now]] && check2[a2[0][now]]==0) dis2[a2[0][now]]=min+a2[2][now];
		now=a2[1][now];
	}
}
void index0(){
	int now=b[1], i;
	for (i=2;i<=n;i++) {
		dis[i] = 999999999;
		check[i] = 0;
	}
	dis[1]=0;
	check[1]=1;
	while (now != -1) {
		dis[a[0][now]]=a[2][now];
		now=a[1][now];
	}
}
void index02(){
	int now=b2[1], i;
	for (i=2;i<=n;i++) {
		dis2[i] = 999999999;
		check2[i] = 0;
	}
	dis2[1]=0;
	check2[1]=1;
	while (now != -1) {
		dis2[a2[0][now]]=a2[2][now];
		now=a2[1][now];
	}
}
void main(){
	int i,j,k,t;
	cin >> alln;
	for(k=0;k<alln;k++){
		sum=0;
		cin >> n >> m;
		for(i=0;i<1000001;i++){b[i]=-1;a[1][i]=-1;a[2][i]=999999999;b2[i]=-1;a2[1][i]=-1;a2[2][i]=999999999;}
		for(i=0;i<m;i++){
			cin >> x >> y >> z;
			if(b[x]==-1){
				b[x]=cnt;
				a[0][cnt]=y;
				a[2][cnt]=z;
				cnt++;
			}
			else{
				t=b[x];
				while(1){
					if(a[1][t]==-1)break;
					else t=a[1][t];
				}
				a[1][t]=cnt;
				a[0][cnt]=y;
				a[2][cnt]=z;
				cnt++;				
			}
			///
			if(b2[y]==-1){
				b2[y]=cnt;
				a2[0][cnt]=x;
				a2[2][cnt]=z;
				cnt++;
			}
			else{
				t=b2[y];
				while(1){
					if(a2[1][t]==-1)break;
					else t=a2[1][t];
				}
				a2[1][t]=cnt;
				a2[0][cnt]=x;
				a2[2][cnt]=z;
				cnt++;
			}
		}
		index0();
		for(i=1;i<n;i++){
			min = 999999999;
			idx = 0;
			for (j=1;j<=n;j++) {
				if (min > dis[j] && check[j] == 0) {
					min = dis[j];
					idx = j;
				}
			}
			sum += min;
			check[idx] = 1;
			index();
		}
		index02();
		for(i=1;i<n;i++){
			min = 999999999;
			idx = 0;
			for (j=1;j<=n;j++) {
				if (min > dis2[j] && check2[j] == 0) {
					min = dis2[j];
					idx = j;
				}
			}
			sum += min;
			check2[idx] = 1;
			index2();
		}
		cout << sum << endl;
	}
}

[mars kaseijin]

looks messy, never mind.

Here is my implementation of Travelling Salesman Problem.
Compiled without any problems using gcc 3.3.3:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>

/*  Define a structure for linked list elements. */
typedef struct ListElmt_ 
{
  void			*data;
  struct ListElmt_	*next;
} ListElmt;

/*  Define a structure for linked lists. */
typedef struct List_ 
{
  int			size;
  
  int			(*match)(const void *key1, const void *key2);
  void			(*destroy)(void *data);
  
  ListElmt		*head;
  ListElmt		*tail;
} List;

/*  -------------------- Public Interface -------------------- */
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list)	((list)->size)

#define list_head(list)	((list)->head)

#define list_tail(list)	((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : \
				     0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)


/*  ------------------------- list_init ------------------------- */
void list_init(List *list, void (*destroy)(void *data)) {

/*  initialize the list. */
  list->size = 0;
  list->destroy = destroy;
  list->head = NULL;
  list->tail = NULL;
  
  return;
}

/*  -------------------- list_destroy -------------------- */
void list_destroy(List *list)
{
  void	*data;
  
/*  remove each element. */
  while(list_size(list) > 0) {
    if (list_rem_next(list, NULL, (void **)&data) == 0 &&
	list->destroy != NULL) {
      
/*  call a user-defined function to free dynamically allocated data. */
      list->destroy(data);
      
    }
    
  }
  
/*  no operations are allowed now, but clear the structure as a precaution. */
  memset(list, 0, sizeof(List));
  
  return;
}

/*  -------------------- list_ins_next -------------------- */
int list_ins_next(List *list, ListElmt *element, const void *data) {
  ListElmt	*new_element;

/*  allocate storage for the element. */
  if((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
    return -1;

/*  insert the element into the list. */
  new_element->data = (void  *)data;

  if(element == NULL) {

/*  handle insertion at the head of the list. */
    if(list_size(list) == 0)
      list->tail = new_element;

    new_element->next = list->head;
    list->head = new_element;
  }
  else {

/*  handle insertion somewhere other than at the head. */
    if(element->next == NULL)
      list->tail = new_element;

    new_element->next = element->next;
    element->next = new_element;
  }
  
/*  adjust the size of the list to account for the inserted element. */
  list->size++;
  return 0;
}

/*  -------------------- list_rem_next -------------------- */
int list_rem_next(List *list, ListElmt *element, void **data) {
  ListElmt	*old_element;

/*  Do not allow removal from an empty list */
  if(list_size(list) == 0)
    return -1;

/*  remove the element from the list. */
  if(element == NULL) {

/*  handle removal from the head of the list. */
    *data = list->head->data;
    old_element = list->head;
    list->head = list->head->next;

    if(list_size(list) == 0)
      list->tail = NULL;
  }

  else {

/*  handle removal from somewhere other than the head. */
    if(element->next == NULL)
      return -1;

    *data = element->next->data;
    old_element = element->next;
    element->next = element->next->next;
    
    if(element->next == NULL)
      list->tail = element;
  }

/*  free the storage allocated by the abstract datatype. */
  free(old_element);

/*  adjust the size of the list to account for the removed element. */
  list->size--;

  return 0;
}

/*  implement set as linked lists. */
typedef List Set;

/*  -------------------- Public Interface -------------------- */
void set_init(Set *set, 
	      int (*match)(const void *key1, const void *key2), void
	      (*destroy)(void *data));

#define set_destroy list_destroy

int set_insert(Set *set, const void *data);

int set_remove(Set *set, void **data);

int set_union(Set *setu, const Set *set1, const Set *set2);

int set_intersection(Set *seti, const Set *set1, const Set *set2);

int set_difference(Set *setd, const Set *set1, const Set *set2);

int set_is_member(const Set *set, const void *data);

int set_is_subset(const Set *set1, const Set *set2);

int set_is_equal(const Set *set1, const Set *set2);

#define set_size(set) ((set)->size)

/*  -------------------- set_init -------------------- */
void set_init(Set *set, 
	      int (*match)(const void *key1, const void *key2),
	      void (*destroy)(void *data)) {

/*  Initialize the set. */
  list_init(set, destroy);
  set->match = match;

  return;
}

/*  -------------------- set_insert -------------------- */
int set_insert(Set *set, const void *data) {

/*  Do not allow the insertion of duplications. */
  if(set_is_member(set, data))
    return 1;

/*  Insert the data. */
  return list_ins_next(set, list_tail(set), data);
}

/*  -------------------- set_remove -------------------- */
int set_remove(Set *set, void **data) {
  ListElmt *member, *prev;

/*  Find the member to remove. */
  prev = NULL;
  for(member = list_head(set); member != NULL; member =
	list_next(member)) {
    if(set->match(*data, list_data(member)))
      break;

    prev = member;
  }

/*  Return if the member was not found. */
  if (member == NULL)
    return -1;

/*  Remove the number. */
  return list_rem_next(set, prev, data);
}

/*  -------------------- set_union -------------------- */
int set_union(Set *setu, const Set *set1, const Set *set2) {
  ListElmt	*member;
  void		*data;

/*  Initialize the set for the union. */
  set_init(setu, set1->match, NULL);

/*  Insert the members of the first set. */
  for(member = list_head(set1); member != NULL; member =
	list_next(member)) {
    data = list_data(member);

    if(list_ins_next(setu, list_tail(setu), data) != 0) {
      set_destroy(setu);
      return -1;
    }
  }

/*  Insert the members of the second set. */
  for(member = list_head(set2); member != NULL; member =
	list_next(member)) {
    if (set_is_member(set1, list_data(member))) {

/*  Do not allow the insertion of duplicates. */
      continue;
    }
    else {
      data = list_data(member);

      if(list_ins_next(setu, list_tail(setu), data) != 0) {
	set_destroy(setu);
	return -1;
      }
    }
  }
  return 0;
}

/*  -------------------- set_intersection -------------------- */
int set_intersection(Set *seti, const Set *set1, const Set *set2) {
  ListElmt	*member;
  void		*data;

/*  Initialize the set for the intersection. */
  set_init(seti, set1->match, NULL);

/*  Insert the members present in both sets. */
  for(member = list_head(set1); member != NULL; member =
	list_next(member)) {
    if(set_is_member(set2, list_data(member))) {
      data = list_data(member);
      if(list_ins_next(seti, list_tail(seti), data) != 0) {
	set_destroy(seti);
	return -1;
      }
    }
  }
  return 0;
}

/*  -------------------- set_difference -------------------- */
int set_difference(Set *setd, const Set *set1, const Set *set2) {
  ListElmt	*member;
  void		*data;

/*  Initialize the set for the difference. */
  set_init(setd, set1->match, NULL);

/*  Insert the members from set1 not in set2. */
  for(member = list_head(set1); member != NULL; member =
	list_next(member)) {
    if(!set_is_member(set2, list_data(member))) {
      data = list_data(member);

      if(list_ins_next(setd, list_tail(setd), data) != 0) {
	set_destroy(setd);
	return -1;
      }
    }
  }
  return 0;
}

/*  -------------------- set_is_member -------------------- */
int set_is_member(const Set *set, const void *data) {
  ListElmt	*member;

/*  Determine if the data is a member of the set. */
  for(member = list_head(set); member != NULL; member =
	list_next(member)) {
    if(!set->match(data, list_data(member)))
      return -1;
  }
  return 0;
}

/*  -------------------- set_is_subset -------------------- */
int set_is_subset(const Set *set1, const Set *set2) {
  ListElmt	*member;

/*  Do a quick test to rule out some cases. */
  if(set_size(set1) > set_size(set2))
    return 0;

/*  Determine if set1 is a subset of set2. */
  for(member = list_head(set1); member != NULL; member =
	list_next(member)) {
    if(!set_is_member(set2, list_data(member))) 
      return 0;
  }
  return 1;
}

/*  -------------------- set_is_equal -------------------- */
int set_is_equal(const Set *set1, const Set *set2) {

/*  Do a quick test to rule out some cases. */
  if(set_size(set1) != set_size(set2))
    return 0;

/*  Sets of the same size are equal if they are subsets. */
  return set_is_subset(set1, set2);
}

/*  Define a structure for adjacency lists. */
typedef struct AdjList_ {
  void		*vertex;
  Set		adjacent;
} AdjList;

/*  Define a structure for graphs. */
typedef struct Graph_ {
  int		vcount;
  int		ecount;
  int		(*match)(const void *key1, const void *key2);
  void		(*destroy)(void *data);
  List		adjlists;
} Graph;

/*  Define colors for vertices in graphs. */
typedef enum VertexColor_ { white, gray, black } VertexColor;

/*  -------------------- Public Interface -------------------- */
void graph_init(Graph *graph, 
		int (*match)(const void *key1, const void *key2), 
		void (*destroy)(void *data));

void graph_destroy(Graph *graph);

int graph_ins_vertex(Graph *graph, const void *data);

int graph_ins_edge(Graph *graph, const void *data1, const void
		   *data2);

int graph_rem_vertex(Graph *graph, void **data);

int graph_rem_edge(Graph *graph, void *data1, void **data2);

int graph_adjlist(const Graph *graph, const void *data, AdjList
		  **adjlist);

int graph_is_adjacent(const Graph *graph, const void *data1, const
		      void *data2);

#define graph_adjlists(graph) ((graph)->adjlists)

#define graph_vcount(graph) ((graph)->vcount)

#define graph_ecount(graph) ((graph)->ecount)

/*  -------------------- graph_init -------------------- */
void graph_init(Graph *graph, 
		int (*match)(const void *key1, const void *key2),
		void (*destroy)(void *data)) {

/*  Initialize the graph. */
graph->vcount = 0;
graph->ecount = 0;
graph->match = match;
graph->destroy = destroy;

/*  Initialize the list of adjacency-list structures. */ 
list_init(&graph->adjlists, NULL);

return;
}

/*  -------------------- graph_destroy -------------------- */
void graph_destroy(Graph *graph) {
  AdjList		*adjlist;
  
/*  Remove each adjacency-list structure and destroy its adjacency
    list. */
  while(list_size(&graph->adjlists) > 0) {
    if(list_rem_next(&graph->adjlists, NULL, (void **)&adjlist) == 0)
      {
	set_destroy(&adjlist->adjacent);

	if(graph->destroy != NULL)
	  graph->destroy(adjlist->vertex);

	free(adjlist);
      }
  }

/*  Destroy the list of adjacency-list structures, which is now empty. */
  list_destroy(&graph->adjlists);

/*  No operations are allowed now, but clear the structure as a precaution. */
  memset(graph, 0, sizeof(Graph));

  return;
}

/*  -------------------- graph_ins_vertex -------------------- */
int graph_ins_vertex(Graph *graph, const void *data) {
  ListElmt		*element;
  AdjList		*adjlist;
  int			retval;

/*  Do not allow the insertion of duplicate vertices. */
  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {
    if(graph->match(data, ((AdjList *)list_data(element))->vertex))
       return 1;
  }

/*  Insert the vertex. */
  if((adjlist = (AdjList *)malloc(sizeof(AdjList))) == NULL)
     return -1;

  adjlist->vertex = (void *)data;
  set_init(&adjlist->adjacent, graph->match, graph->destroy);

  if((retval = list_ins_next(&graph->adjlists,
			     list_tail(&graph->adjlists), 
			     adjlist)) != 0) {
    return retval;
  }

/*  Adjust the vertex count to account for the inserted vertex. */
  graph->vcount++;

  return 0;
}

/*  -------------------- graph_ins_edge -------------------- */
int graph_ins_edge(Graph *graph, const void *data1, const void *data2)
{
  ListElmt		*element;
  int			retval;

/*  Do not allow insertion of an edge without both its vertices in the
    graph. */
  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {
    if(graph->match(data2, ((AdjList *)list_data(element))->vertex))
      break;
  }

  if(element == NULL)
    return -1;

  for(element = list_head(&graph->adjlists); element != NULL; element =
	list_next(element)) {
    if(graph->match(data1, ((AdjList *)list_data(element))->vertex))
      break;
  }

  if(element == NULL)
    return -1;

/*  Insert the second vertex into the adjacency list of the first
    vertex. */
  if((retval = set_insert(&((AdjList *)list_data(element))->adjacent,
			  data2)) != 0) {
    return retval;
  }

/*  Adjust the edge count to account for the inserted edge. */
  graph->ecount++;

  return 0;
}

/*  -------------------- graph_rem_vertex -------------------- */
int graph_rem_vertex(Graph *graph, void **data) {
  ListElmt		*element, *temp, *prev;
  AdjList		*adjlist;
  int			found;

/*  Traverse each adjacency list and the vertices it contains. */
  prev = NULL;
  found = 0;

  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {

/*  Do not allow removal of the vertex if it is in an adjacency
    list. */
    if(set_is_member(&((AdjList *)list_data(element))->adjacent,
		     *data))
      return -1;

/*  Keep a pointer to the vertex to be removed. */
    if(graph->match(*data, ((AdjList *)list_data(element))->vertex)) {
      temp = element;
      found = 1;
    }

/*  Keep a pointer to the vertex before the vertex to be removed. */
    if(!found)
      prev = element;
  }

/*  Return if the vertex was not found. */
  if(!found)
    return -1;

/*  Do not allow removal of the vertex if its adjacency list is not empty. */
  if(set_size(&((AdjList *)list_data(temp))->adjacent) > 0)
    return -1;

/*  Remove the vertex. */
  if(list_rem_next(&graph->adjlists, prev, (void **)&adjlist) != 0)
    return -1;

/*  Free the storage allocated by the abstract datatype. */
  *data = adjlist->vertex;
  free(adjlist);

/*  Adjust the vertex count to account for the removed vertex. */
  graph->vcount--;

  return 0;
}

/*  -------------------- graph_rem_edge -------------------- */
int graph_rem_edge(Graph *graph, void *data1, void **data2) {
  ListElmt		*element;

/*  Locate the adjacency list for the first vertex. */
  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {
    if(graph->match(data1, ((AdjList *)list_data(element))->vertex))
      break;
  }

  if(element == NULL)
    return -1;

/*  Remove the second vertex from the adjacency list of the first
    vertex. */
  if(set_remove(&((AdjList *)list_data(element))->adjacent, data2) !=
     0)
    return -1;

/*  Adjust the edge count to account for the removed edge. */
  graph->ecount--;

  return 0;
}

/*  -------------------- graph_adjlist -------------------- */
int graph_adjlist(const Graph *graph, const void *data, AdjList
		  **adjlist) {
  ListElmt		*element, *prev;

/*  Locate the adjacency list for the vertex. */
  prev = NULL;

  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {
    if(graph->match(data, ((AdjList *)list_data(element))->vertex))
      break;

    prev = element;
  }

/*  Return if the vertex was not found. */
  if(element == NULL)
    return -1;

/*  Pass back the adjacency list for the vertex. */
  *adjlist = list_data(element);

  return 0;
}

/*  -------------------- graph_is_adjacent -------------------- */
int graph_is_adjacent(const Graph *graph, const void *data1, const
		      void *data2) {
  ListElmt		*element, *prev;
  
/*  Locate the adjacency list of the first vector. */
  prev = NULL;

  for(element = list_head(&graph->adjlists); element != NULL; element
	= list_next(element)) {
    if(graph->match(data1, ((AdjList *)list_data(element))->vertex))
      break;

    prev = element;
  }

/*  Return if the first vertex was not found. */
  if(element == NULL)
    return 0;

/*  Return whether the second vertex is in the adjacency list of the
    first. */
  return set_is_member(&((AdjList *)list_data(element))->adjacent,
		       data2);
}

/*  Define a structure for vertices in minimum spanning trees.	*/
typedef struct MstVertex_ {
  void	      *data;
  double      weight;
  
  VertexColor color;
  double      key;
  
  struct MstVertex_ *parent;
} MstVertex;

/*  Define a structure for vertices in shortest-path problems.	*/
typedef struct PathVertex_  {
  void	      *data;
  double      weight;
  
  VertexColor color;
  double      d;
  
  struct PathVertex_  *parent;
} PathVertex;

/*  Define a structure for vertices in traveling-salesman problems. */
typedef struct TspVertex_ {
  void	      *data;
/*  double      x, y;*/

  VertexColor color;
} TspVertex;

typedef struct ROUTE {
  int origin, dest;
  unsigned long price;
} route;

/*  --------------------- Public Interface -----------------------  */
int tsp(List *vertices, const TspVertex *start, List *tour, int (*match)
(const void *key1, const void *key2));


/*  --------------------------- tsp ------------------------------  */
int tsp(List *vertices, const TspVertex *start, List *tour, int
  (*match)(const void *key1, const void *key2))	{
  TspVertex	  *tsp_vertex,
		  *tsp_start,
		  *selection;

  ListElmt	  *element;

  unsigned long	  minimum,
		  distance;
		  /* x, y */

  int		  found,
		  i;

/*  Initialize the list for the tour. */
  list_init(tour, NULL);

/*  Initialize all of the vertices in the graph.  */
  found = 0;

  for(element = list_head(vertices); element != NULL; element =
    list_next(element))	{
    tsp_vertex = list_data(element);

    if(match(tsp_vertex, start))  {

/*  Start the tour at the start vertex.	*/
      if(list_ins_next(tour, list_tail(tour), tsp_vertex) != 0)	{
	list_destroy(tour);
	return -1;
      }

/*  Save the start vertex and its coordinates.	*/
      tsp_start = tsp_vertex;
/*      x = tsp_vertex->x;
      y = tsp_vertex->y;*/

/*  Color the start vertex black. */
      tsp_vertex->color = black;
      found = 1;
    }
    else  {

/*  Color all other vertices white. */
      tsp_vertex->color = white;
    }
  }

/*  Return if the start vertex was not found. */
  if(!found)  {
    list_destroy(tour);
    return -1;
  }

/*  Use the nearest-neighbour heuristic to compute the tour.  */
  i = 0;
  
  while(i < list_size(vertices) - 1) {

/*  Select the white vertex closest to the previous vertex in the tour.	*/
    minimum = 1000000000;

    for(element = list_head(vertices); element != NULL; element =
      list_next(element)) {

      tsp_vertex = list_data(element);

      if(tsp_vertex->color == white)  {
      /*distance = sqrt(pow(tsp_vertex->x-x, 2.0) + pow(tsp_vertex->y-y, 2.0));*/
	distance = ((route*)tsp_vertex->data)->price;
	
	if(distance < minimum)	{
	  minimum = distance;
	  selection = tsp_vertex;
	}
      }
    }

/*  Save the coordinates of the selected vertex.  */
/*    x = selection->x;
    y = selection->y;*/

/*  Color the selected vertex black. */
    selection->color = black;

/*  Insert the selected vertex into the tour. */
    if(list_ins_next(tour, list_tail(tour), selection) != 0)  {
      list_destroy(tour);
      return -1; 
    }

/*  Prepare to select the next vertex.	*/
    i++;
  }

/*  Insert the start vertex again to complete the tour.	*/
  if(list_ins_next(tour, list_tail(tour), tsp_start) != 0)  {
    list_destroy(tour);
    return -1;
  }

  return 0;
}

int compar(const void* k1, const void* k2) {  /* key is origin */
  TspVertex *t1 = (TspVertex*)k1;
  TspVertex *t2 = (TspVertex*)k2;
  return ((route*)t1->data)->origin == ((route*)t2->data)->origin ? 1 : 0;
}

int main() {
  unsigned long i;
  int j , k;
  List *vertices, *tour;
  ListElmt *cur;
  scanf("%ld\n", &i);

  for(j = 0; j < i ; j++) {
    int stops, buslines;
    unsigned long tot = 0;
    scanf("\n%d %d", &stops, &buslines);

    vertices = (List*)malloc(sizeof(List));
    tour = (List*)malloc(sizeof(List));
    TspVertex *start = (TspVertex*)malloc(sizeof(TspVertex));

    list_init(vertices, NULL);
     
    for(k = 0; k < buslines; k++) {
      route *r = (route*)malloc(sizeof(route));
      TspVertex *tsp = (TspVertex*)malloc(sizeof(TspVertex));
      scanf("\n%d %d %ld", &(r->origin), &(r->dest), &(r->price));

      if(k == 0) 
	start->data = (void*)r;	

      tsp->data = (void*)r;
      list_ins_next(vertices, list_tail(vertices), (void*)tsp);
    } 

    printf("\n%d", tsp(vertices, start, tour, &compar));
    for(cur = list_head(tour); cur ; cur = cur->next) {
      TspVertex* t = cur->data;
      tot += ((route*)t->data)->price;
      printf("\nTspVertex: %d %d %ld", ((route*)t->data)->origin, ((route*)t->data)->dest,
	    ((route*)t->data)->price);
    }

    printf("\t%ld\n", tot);
    free(vertices);
    free(tour);
    free(start);
  }
  
  return 0;
}

[sds1100]

what's mean???
your source CE;;;
what`
please help me -_ -;;

[mars kaseijin]

The algo needs tweaking so that it could fit p721.
Will need some re-definition of structs to represent sample input...
otherwise, the algo takes care of the rest.

Besides this algo, i am currently implementing Dikestra's algo + weighted graph
for this problem. It will go far...

BTW, do you play free civilization for leisure?