[OJ]1014:西湖三人行

2019-2-19 写技术

Description

去年10月份,FightOn队伍的三个人YZW、HKX、WX在参加完杭州赛区后想到杭州最有名的西湖去玩。他们所能选择的交通方式只有三种:

  1. 走路,速度为1m/s,每人每千米花费1元钱(因为他们会消耗体力,需要买水、食物等)。
  2. 搭公交,速度为4m/s,每人2元,每条公交路线都按照一定的方向。
  3. 打的,速度为8m/s,起步价3千米内10元,以后每千米2元,每个站点都有的士。

当然杭州的交通秩序不像长沙,所以如果想改变交通方式只能在每个站点改换。三个人现在囊中羞涩,但又比较急,所以他们想在不超过L(0<L<101)元钱的前提下尽快到达西湖。

此处假设三人在站点改换交通方式时不考虑等待时间,并且公交和的士始终匀速。

Input

第一行一个数字T表示接下来有T组数据(T<11)

每组数据的第一行有6个整数LNMSTB。表示图共有N个站点(N<100)M表示共有M条路(M<1000),起点为S,西湖的位置为T(S≠T),共有B条公交线路(B<200)

接下来M行,每行3个整数uvw,表示站点uv之间存在一条路距离为w千米(0<w<10)uv可以互达. 此处假设任意两点之间最多有一条直接相连的路。

接下来B行,每行第一个为K(1<K<20),表示当前公交车共经过K个站点,接下来K个整数,表示当前公交车依次经过K个站点的编号(此K个站点保证两两互达,此路线并不代表公交车可以原路返回)。

Output

如果能够花费不超过L元达到西湖,则输出达到西湖所需的最少秒数,否则输出“no”(不带引号)。


#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

发表评论:

Powered by anycle 湘ICP备15001973号