现在，黎恒健与YJY由于身处异地，非常迫切地想在最短的时间内相遇，然后干一架。但是由于双方都在努力地编程序想干掉对方，所以他们希望你来帮他们找到一个最好的方案使得相遇的时间最短。
　　   在此我们定义"相遇"为：两个人皆在同一个有编号的星球上就可以了，并且这两个人均可以站在原地等另外一个人。也就是说，在这里我们不考虑两人在宇宙中间相遇。

输入数据第一行：N和M（用空格隔开） 表示这是一个N个点的图并且有M条边
第二行到第M+1行 为这个图的详细信息。
　　  每行共有被空格隔开的三个数：a b c。表示编号为a的星球到编号为b的星球
　　  有一个双向边，并且要过这条双向边所需要花费的时间为c。
最后一行有两个数：Y和T，Y表示黎恒健所在星球（也就是月球），T表示YJY所处的
星球（也就是天狼星）

输出只有一行，D，表示二者"相遇"的最短时间。当然，如果无法相遇则输出"They are all died!"

3 3

1 2 1

2 3 1

1 3 1

1 3

1

[数据范围]每组都是n=5000 m=5000 并且保证运算过程中的所有值都不会超过117901063

#include <cstring>

#include <cstdio>

#include <queue>

#define N 5005

using namespace std;

bool vis[N];

int n,m,S,T,cnt,ans=0x7fffffff,far[][N],to[N<<],val[N],head[N],nextt[N<<];

struct node

{

    int x,y;

    bool operator<(node a)const

    {

        return y>a.y;

    }

};

priority_queue<node>q;

void dijkstra(int s,int *dis)

{

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;++i) dis[i]=0x7fffffff;

    dis[s]=;

    q.push((node){s,dis[s]});

    for(node now;!q.empty();)

    {

        now=q.top();q.pop();

        if(vis[now.x]) continue;

        vis[now.x]=true;

        for(int i=head[now.x];i;i=nextt[i])

        {

            int v=to[i];

            if(dis[v]>dis[now.x]+val[i])

            {

                dis[v]=dis[now.x]+val[i];

                if(!vis[v]) q.push((node){v,dis[v]});

            }

        }

    }

}

inline int min(int a,int b) {return a>b?b:a;}

inline int max(int a,int b) {return a>b?a:b;}

inline void ins(int u,int v,int w)

{

    nextt[++cnt]=head[u];to[cnt]=v;val[cnt]=w;head[u]=cnt;

    nextt[++cnt]=head[v];to[cnt]=u;val[cnt]=w;head[v]=cnt;

}

int main(int argc,char *argv[])

{

    scanf("%d%d",&n,&m);

    for(int a,b,c;m--;)

    {

        scanf("%d%d%d",&a,&b,&c);

        ins(a,b,c);

    }

    scanf("%d%d",&S,&T);

    dijkstra(S,far[]);

    dijkstra(T,far[]);

    for(int i=;i<=n;++i) ans=min(ans,max(far[][i],far[][i]));

    ans!=0x7fffffff?printf("%d\n",ans):printf("They are all died!");

    return ;

}