上面那个不加删除，下面那个加删除。。。

删除一次要splay 两次，而且并不能降低树的高度。。。

听说splay有不可改进的常数 =3 。 2*3=6 。。。常数太大了。。。

mycode：（删除的确写丑了？？）

写了各种Splay，以下这个版本最让我满意：）。。所以叫“终极”。。。

风格飘逸，时间短，代码短也没有恶意缩行。融合各神犇之精华。

非常满意。不加读入优化BZOJ46名。一会儿我试试读入优化的效果。

加读入优化以后

以下代码

非常经典一题，我竟然交了那么十几次。。。TnT。。。

注意这么几个问题：

1、千万不要只连单向边否则遇上这种例子就跪了。。。

3

1 2

3 2

2、poj3107 sgu149 ural1056 poj3099 noi03逃学的孩子。。。1=6。。。

3、至于算法:ans[x]=max(x->son->size,n- x->size)

画个图就可以意会了 ：）

4、从poj上搬运几组小数据

8
1 2
1 3
1 4
1 5
5 6
6 7
7 8

ans:
4 2
1 5

=====。。。。。==========。。。。。=====

10
1 2
1 3
1 4
1 5
5 6
6 7
7 8
5 9
4 10

ans:
5 2
1 5

=====。。。。。==========。。。。。=====

11
1 2
1 3
2 4
2 5
4 8
5 9
3 6
3 7
10 1
11 2

ans:
5 1
2

最短路。。。就是在SPFA是要现算两点之间在这一时刻的dist（包括等的时间）。主要就是这个东东。。。其他就没什么了

写的时候差点要跪。。。但是竟然一次AC了~非常高兴。

听说Sgu不存代码，于是写日志吧。。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define rep(i,n) for(int i=0;i<(n);i++)
#define maxn 307
#define pb push_back
using namespace std;
const int inf=~0u>>2;
struct edge
{
	int to,c;
};

vector<edge>G[maxn];
void add(int from,int to,int c)
{
	G[from].pb((edge){to,c});
	G[to].pb((edge){from,c});
}
int d[maxn],v[maxn],pre[maxn],s,t,r[maxn],T[maxn][2];
char C[maxn][3];
queue<int>Q;
int Dist(int x,int i,int t)
{
	int y=G[x][i].to;
	bool f1=C[x][0]=='B'?0:1,f2=C[y][0]=='B'?0:1;
	int r1=r[x],r2=r[y];
	int t1=t%(T[x][0]+T[x][1]),t2=t%(T[y][0]+T[y][1]);
	if(r1>=t1)r1-=t1;
	else
	{
		r1+=T[x][f1^=1];
		if(r1>=t1)r1-=t1;
		else
		{
			r1+=T[x][f1^=1];
			r1-=t1;
		}
	}
	if(r2>=t2)r2-=t2;
	else
	{
		r2+=T[y][f2^=1];
		if(r2>=t2)r2-=t2;
		else
		{
			r2+=T[y][f2^=1];
			r2-=t2;
		}
	}
	if(r1==0)r1+=T[x][f1^=1];
	if(r2==0)r2+=T[y][f2^=1];
	if(f1==f2)return G[x][i].c;
	int c=3,tt=0;
	while(c--)
	{
		int mi=min(r1,r2);
		tt+=mi;
		r1-=mi;r2-=mi;
		if(r1==0)r1+=T[x][f1^=1];
		if(r2==0)r2+=T[y][f2^=1];
		if(f1==f2)return G[x][i].c+tt;
	}
	return inf;	
}
void spfa()
{
	memset(d,127,sizeof(d));
	memset(v,0,sizeof(v));
	Q.push(s);
	v[s]=true;
	d[s]=0;
	while(Q.size())
	{
		int x=Q.front();Q.pop();
		v[x]=false;
		rep(i,G[x].size())
		{
			edge&e=G[x][i];
			int dist=Dist(x,i,d[x]);
			if(dist==inf)continue;
			if(d[e.to]>d[x]+dist)
			{
				d[e.to]=d[x]+dist;
				pre[e.to]=x;
				if(!v[e.to])
				{
					v[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
}

vector<int>ans;	
int main()
{
	//freopen("103.in","r",stdin);
	int n,m,a,b,c;
	scanf("%d%d",&s,&t);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s%d%d%d",&C[i],&r[i],&T[i][0],&T[i][1]);
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	spfa();
	if(d[t]>=inf){printf("0\n");return 0;}
	//for(int i=1;i<n;i++)printf("%d ",d[i]);	
	printf("%d\n",d[t]);
	int u=t;
	while(u!=s)
	{
		ans.pb(u);
		u=pre[u];
	}
	ans.pb(s);
	for(int i=ans.size()-1;i>0;i--)printf("%d ",ans[i]);
	printf("%d\n",ans[0]);
	return 0;
}