苗火 Nicholas

[OJ]1014:西湖三人行

2019-2-19 萧 写技术

#include <stdio.h>

#define MAX_VERTICES 100
#define MAX_EDGES 1000
#define MAX_BUSES 200
#define MAX_DURATION 1000000

#define TAXI_KM_TIME 125
#define BUS_KM_TIME 250
#define WALK_KM_TIME 1000

typedef struct _Graph{
	int vertex_num;
	int edge_num;
	int vertices[MAX_VERTICES];
	int edges[MAX_VERTICES][MAX_VERTICES];	
	int visited[MAX_VERTICES];
}Graph;

typedef struct _Bus{
	int bus_num;
	int lines[MAX_BUSES][MAX_VERTICES];	
}Bus;

typedef struct _Route{
	int vertex;
	int method;
}Route;

Route route[655350];
int top = -1;

void graph_init(Graph *G){
	int i,j;
	G->vertex_num = 0;
	G->edge_num = 0;
	for(i = 0; i < MAX_VERTICES; i++){
		G->vertices[i] = -1;
		G->visited[i] = 0;
		for(j = 0; j < MAX_VERTICES; j++){
			G->edges[i][j] = -1;
		}
	}	
}

int graph_first_vertex(Graph *G, int root){
	int i;
	for(i=1; i<MAX_VERTICES; i++){
		if(G->edges[root][i] > 0){
			return i;
		}
	}
	return -1;
}

int graph_next_vertex(Graph *G, int root, int from){
	int i;
	for(i=from+1; i<MAX_VERTICES; i++){
		if(G->edges[root][i] > 0){
			return i;
		}
	}
	return -1;
}




/* money means the money remained, 
   method means traffic method, -1 stands for taxi, -2 stands for walk, others stands for bus 
*/
int graph_bfs(Graph *G, int from, int dst, int money, int last_method, int last_dist, Bus *B, int duration){
	int first,next,tmp,min,cost,i,j;
	int _duration,_money,_method,_next;
	int duration_taxi, duration_bus, duration_walk;
	int a_top, b_top, walk_top, k, m;

	int mm,nn;
	if(from == dst){
		return duration;	
	}
	if(money<0){
		return -1;
	}

	/* Find first  */
	a_top = b_top = -1;
	next = graph_first_vertex(G, from);
	min = MAX_DURATION;
	while(next>=0){
		if(G->visited[next] != 1){
			G->visited[next] = 1;

			cost = G->edges[from][next];
			//Taxi
			_duration = duration + TAXI_KM_TIME * cost;
			if(last_method == -2){
				tmp = 3 - last_dist;
				if(tmp > 0){
					_money = money - (cost - tmp) * 2;	
				}else{
					_money = money - cost * 2;	
				}
				last_dist += cost;
			}else{
				_money = money - 10;
				tmp = cost - 3;
				if(tmp > 0){
					_money -= tmp * 2;
				}
				last_dist = cost;
			}
			if(_money >= 0){
				b_top = top;
				_duration = graph_bfs(G, next, dst, _money, -2, last_dist, B, _duration); 
				if(_duration > 0 && _duration < min){
					min = _duration;
					_method = -2;
					_next = next;

					if(a_top >= 0){
						m = a_top;
						for(k=b_top+1; k<=top; k++){
							route[++m].vertex = route[k].vertex;
							route[m].method = route[k].method;
						}
						top = m;
					}else{
						a_top = b_top;
					}
				}else{
					top = b_top;
					b_top = -1;
				}
			}


			//Bus
			for(i=0; i<B->bus_num; i++){
				j=1;
		
				while(j < MAX_VERTICES && B->lines[i][j]>=0
					&& (B->lines[i][j-1] != from || B->lines[i][j] != next) ){	
					j++;
				}
				if(j == MAX_VERTICES || B->lines[i][j] < 0){
					continue;		
				}
			

				_duration = duration + BUS_KM_TIME * cost;
				_money = money;
				if(last_method != i){
					_money -= 2*3;
				}
			
				if(_money >= 0){
					b_top = top;
					_duration = graph_bfs(G, next, dst, _money, i, 0, B, _duration);
					if(_duration > 0 && _duration < min){
						min = _duration;
						_method = i;
						_next = next;
			
						if(a_top >= 0){
							m = a_top;
							for(k=b_top+1; k<=top; k++){
								route[++m].vertex = route[k].vertex;
								route[m].method = route[k].method;
							}
							top = m;
						}else{
							a_top = b_top;
						}
					}else{
						top = b_top;
						b_top = -1;
					}

				}
			}

			//Walk
			_duration = duration + WALK_KM_TIME * cost;
			_money = money - 1*3*cost;

			if(_money >= 0){
				b_top = top;
				_duration = graph_bfs(G, next, dst, _money, -1, 0, B, _duration);	
				if(_duration > 0 && _duration < min){
					min = _duration;
					_method = -1;
					_next = next;

					if(a_top >= 0){
						m = a_top;
						for(k=b_top+1; k<=top; k++){
							route[++m].vertex = route[k].vertex;
							route[m].method = route[k].method;

						}
						top = m;
					}else{
						a_top = b_top;
					}
				}else{
					top = b_top;
					b_top = -1;
				}

			}

			G->visited[next] = -1;
		}else{
		}
		next = graph_next_vertex(G, from, next);
	}
	G->visited[from] = 1;
	if(min == MAX_DURATION){
		return -1;
	}
//	printf(" %d->%d (%d)\n", from, _next, _method);
	route[++top].vertex = _next;
	route[top].method = _method;
	return min;
}

void bus_init(Bus *B){
	int i,j;
	B->bus_num = 0;
	for(i=0; i<MAX_BUSES; i++){
		for(j=0; j<MAX_VERTICES; j++){
			B->lines[i][j] = -1;
		}
	}
}

void main(){
	int tests, l, n, m, s, t, b;
	int u,v,w;
	int duration;
	Graph G;
	Bus B;
	
	
	scanf(" %d", &tests);
	while(tests--){
		scanf(" %d %d %d %d %d %d", &l, &n, &m, &s, &t, &b);
		graph_init(&G);
		G.vertex_num = n;
		G.edge_num = m;
		while(m--){
			scanf(" %d %d %d", &u, &v, &w);
			G.edges[u][v] = w;
			G.edges[v][u] = w;
		}
		bus_init(&B);
		B.bus_num = b;	
		for(n=0; n<b; n++){
			scanf(" %d", &u);
			m = 0;
			for(m=0; m<u; m++){
				scanf(" %d", &v);
				B.lines[n][m] = v;	
			}
		}

		G.visited[s] = 1;
		duration = graph_bfs(&G, s, t, l, -2, 0, &B, 0);	
		if(duration<0){
			printf("no\n");
		}else{
			printf("%d\n", duration);
		}
		
		while(top>=0){
		//	printf(" %d---(%d)\n", route[top].vertex, route[top].method);
			top--;
		}
	}	
}

标签: C