评测机FP版本太老，导致C++的速度超过FP速度的N^N^N^N^N倍。（数据范围：N>=100）
/*
查看题目 Show Problem
题目:布布的森林探险
问题编号:462 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
尚未设置
描述
布布是一只喜欢探险的猴子。有一次，她在森林里迷路了（不仅仅是去探险，还要去找香蕉和桃子），森林里的每个地方都有一个编号1～n。幸好她所在的森林有路标，这些路标会告诉她从她所在的地方可以到达哪里，以及到达另一个地方的时间。布布所在的地方为s地，他想去k地玩，这个森林的出口是t地。但是布布找了一天的香蕉和桃子，很累了，更重要的是她也很饿……她必须在m时间内到达k地再出森林。所有的路标的起点终点值均包含上文的s，k和t。
输入格式
第一行是n，s，t，k，m，其中n≤1000；
第二行是bian，代表边的数目，bian≤200000；
接下来bian行，每行3个数，分别为ui，vi，ri，表示从ui地到vi地需要ri个单位时间。（ri≤maxlongint）
注意：
1. 从a 到b的路径 不意味着b也可以到a ；
2. 必须先到k 才能到t ；
3. 所有数据均为正整数，且答案小于maxlongint。
输出格式
如果布布可以在规定时间内走出森林，则第一行输出‘Yes’，否则输出‘No’；第二行输出布布走出森林的最少时间。
样例输入
5 1 5 2 10
5
1 2 3
1 4 1
2 4 5
4 5 2
2 3 1
样例输出
Yes
10
*/
#include<climits>
#include<iostream>
using namespace std；
int n,s,t,k,m,b；
struct link{
int adjvex,len；
link *next；
}；
struct point{
link *head；
} ps[1001]；
int que[100001],dis[1001],front,rear；
bool mark[1001]；
void spfa(int i){
memset(mark,false,sizeof(mark))；
for (int o=1；o<=n；++o)
dis[o]=INT_MAX；
front=rear=0；
que[front]=i；
++front；
dis[i]=0；
mark[i]=true；
while (front>rear){
int j=que[rear]；
// cout<<j<<’ ’<<dis[j]<<endl；
++rear；
rear%=100001；
mark[j]=false；
if (dis[j]==INT_MAX) continue；
link *p；
p=ps[j].head；
while (p!=NULL){
// cout<<p->adjvex<<’ ’<<p->len<<’ ’<<dis[p->adjvex]<<endl；
if (dis[p->adjvex]>dis[j]+p->len){
dis[p->adjvex]=dis[j]+p->len；
// cout<<j<<" changed "<<p->adjvex<<endl；
if (!mark[p->adjvex]){
que[front++]=p->adjvex；
mark[p->adjvex]=true；
front%=100001；
}
}
p=p->next；
}
}
}
int main (void){
int u,v,r；
cin>>n>>s>>t>>k>>m>>b；
for (int i=1；i<=n；++i) ps[i].head=NULL；
for (int i=0；i<b；++i){
scanf("%d %d %d",&u,&v,&r)；
link *p；
p=new link；
p->adjvex=v；
p->len=r；
p->next=ps[u].head；
ps[u].head=p；
}
spfa(s)；
int f=dis[k]；
// for (int i=1；i<=n；++i)
// cout<<dis[i]<<’ ’；
// cout<<endl；
spfa(k)；
// for (int i=1；i<=n；++i)
// cout<<dis[i]<<’ ’；
// cout<<endl；
f+=dis[t]；
if (f>m) printf ("No\n")；
else printf ("Yes\n")；
cout<<f；
// while (1)；
return 0；
}
using namespace std；
int N,S,T,K,M；
int c,**Map,*Search；
bool *bo；
int Dij(int x,int y)
{
for (int i=1；i<=N；i++){
bo[i]=true；
Search[i]=Map[x][i]；
}
bo[x]=false；
for (int j=1；j<N；j++){
int p,minn=0x3FFFFFFF；
for (int i=1；i<=N；i++)
if (bo[i] && Search[i]<minn){
minn=Search[i]；
p=i；
}
bo[p]=false；
for (int i=1；i<=N；i++)
if (bo[i] && Map[p][i]+Search[p]<Search[i])
Search[i]=Map[p][i]+Search[p]；
}
return Search[y]；
}
int main()
{
scanf("%d%d%d%d%d",&N,&S,&K,&T,&M)；
Map=new int*[N+1]；
Search=new int[N+1]；
bo=new bool[N+1]；
for (int i=1；i<=N；i++){
Map[i]=new int[N+1]；
for (int j=1；j<=N；j++)
Map[i][j]=9999999；
}
scanf("%d",&c)；
for (int i=1；i<=c；i++){
int x,y,ce；
scanf("%d%d%d",&x,&y,&ce)；
if (Map[x][y]>ce)
Map[x][y]=ce；
}
int scx=Dij(S,T)+Dij(T,K)；
if (scx>M) cout<<"No\n"；
else cout<<"Yes\n"；
cout<<scx<<endl；
delete Search；
delete bo；
for (int i=1；i<=N；i++)
delete Map[i]；
delete Map；
return 0；
}