苹果运输

题目描述:

Bessie 将要把两箱脆脆的红苹果送给她的两个朋友 。当然，像常见的图一样有 \( C ( 1 \le C \le  2*10^5 ) \) 条牛径连接着 \( P (1 \le  P \le 1*10^5 ) \) 个牧场（ 为了方便起见，标号\( 1 \dots p \)  ），牛径是双向的，每条路都有一个长度。而且我们总是能从一个牧场到另外一个牧场。每条牛径连接两个不同的牧场 \( P1_i ( 1 \le P1_i \le P)  \)  和  \( P2_i (1 \le P2_i \le P ) \) ，长度为 \( D_i \) 。 所有路径长度之和不超过 \( 2*10^9 \) 。

Bessie从牧场 \( PB ( 1 \le PB \le P \) 出发，求Bessie把苹果送给她的两个朋友（ 分别在  \( PA1 (1 \le  PA1 \le  P) \) 和 \( PA2 ( 1 \le PA2 \le P ) \)  ) 所需走的最短路程，（无所谓先把苹果送给谁）。这三个牧场都是不同的。

考虑下面这个例子，括号内的是牧场编号，其余是路径长度。

 

如果 Bessie从[5]出发，把苹果送到[1]和[4]，她走的路径是这样的 

      5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1* 

总长 12.

输入格式:

* Line 1 包含五个用空格分开的整数 \( C, P, PB,PA1 \) 和  \( PA2 \) 。

* Lines 2: Line i+1 描述牛径 i，其端点 \( P1_i, P2_i \) 和长度 \( D_i \) 。

输出格式:

* Line 1: Bessie所需走的最小路程。

样例输入:

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

样例输出:

12

提示:

图的存储方式：

存储1：
二维数组，注意存储空间

存储2：
struct data{
	int to, val;
};
vector< data > a[100001];

存储3：
struct node{
	int to,val,next;
}edge[ 400001 ];  //边的数量
int num, head[ 20001 ];   //顶点的数量
void add( int u, int v, int w ){
	edge[ ++num ].to = v;
	edge[ num ].val = w;
	edge[ num ].next = head[u];
	head[ u ] = num;
}

存储4：
和存储3原理一样，只是用多个独立的数组存储
int tot, to[ N ], val[ N ], _next[ N ], _head[ N ];
void add( int x, int y, int z ){
	to[ ++tot ] = y;
	val[ tot ] = z;
	_next[ tot ] = _head[x];
	_head[x] = tot;
}
存储3和存储4称为链式前向星，由某个顶点出发的边的顶点构成一条链，链的尾结点指针（next) 为0。

时间限制: 1000ms
空间限制: 256MB

---