去年10月份,FightOn队伍的三个人YZW、HKX、WX在参加完杭州赛区后想到杭州最有名的西湖去玩。他们所能选择的交通方式只有三种：
1m/s，每人每千米花费1元钱（因为他们会消耗体力,需要买水、食物等）。4m/s，每人2元,每条公交路线都按照一定的方向。8m/s，起步价3千米内10元,以后每千米2元,每个站点都有的士。
当然杭州的交通秩序不像长沙，所以如果想改变交通方式只能在每个站点改换。三个人现在囊中羞涩,但又比较急,所以他们想在不超过L(0<L<101)元钱的前提下尽快到达西湖。
此处假设三人在站点改换交通方式时不考虑等待时间，并且公交和的士始终匀速。
第一行一个数字T表示接下来有T组数据(T<11)。
每组数据的第一行有6个整数L，N，M，S，T，B。表示图共有N个站点(N<100)，M表示共有M条路(M<1000)，起点为S，西湖的位置为T(S≠T)，共有B条公交线路(B<200)。
接下来M行，每行3个整数u，v，w，表示站点u与v之间存在一条路距离为w千米(0<w<10)，u与v可以互达. 此处假设任意两点之间最多有一条直接相连的路。
接下来B行，每行第一个为K(1<K<20)，表示当前公交车共经过K个站点，接下来K个整数，表示当前公交车依次经过K个站点的编号(此K个站点保证两两互达，此路线并不代表公交车可以原路返回)。
如果能够花费不超过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--;
}
}
}