这周下的雪好大好大，不过这正和KK学长之意。因为他要去陪学妹滑雪，谁知调皮的学妹要和KK比赛，无奈的KK只能应战。已知比赛场地有n个站点，m条路线。比赛起点是第一个站点，终点是第n个站点，先到达终点的人是胜者(如果KK和学妹同时到，KK会认输)。现在KK为了显示学长风范，决定让学妹先滑T秒。但是到了比赛的时候，KK就有点后悔了。已知学妹到达终点需要时间Tg秒，KK每秒可以滑k米。现在问你KK在最优情况下能否赢得比赛。

给定一个整数t，表示有t(t<=20)组测试数据。每组测试数据有两个整数n(1<=n<=1000)，m(1<=m&lt;=10000)，接下来m行表示路线，每行三个整数a，b，c分别表示路线起点，终点，长度。最后一行有两个个整数T(1<=T&lt;=10)，Tg(1<=Tg<=10000)和一个实数k(0<=k<=200)表示上面提到的信息。

若KK可以获胜输出"Good job,KK!"，否则输出"What a pity!"。输出占一行。

要求精度>=1e-3

真是最艰难的一道题，想得太多，wa10次，差一点就金奖了！！！！！真是打脸

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f

#define N 1100

int map[N][N];

int vis[N];

int dis[N];

int n,m;

void dijst()

{

    int minn,i,j,k,sum;

    memset(vis,0,sizeof(vis));

    for(i=2;i<=n;i++)

    dis[i]=map[1][i];

    vis[1]=1;

    for(j=1;j<=n;j++)

    {

        minn=INF;

        k=0;

        for(i=2;i<=n;i++)

        {

            if(!vis[i]&&dis[i]<minn)

            {

                k=i;

                minn=dis[i];

            }

        }

        vis[k]=1;

        for(i=2;i<=n;i++)

        {

            if(!vis[i]&&dis[k]+map[k][i]<dis[i])

                dis[i]=dis[k]+map[k][i];

        }

    }

}

int main()

{

    int t,a,b,c,i,j;

    scanf("%d",&t);

    while(t--)

    {

        memset(map,INF,sizeof(map));

        memset(dis,INF,sizeof(dis));

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

        while(m--)

        {

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

            if(c<map[a][b])

            map[a][b]=map[b][a]=c;

        }

        dijst();

        int T,Tg;

        double k;

        scanf("%d%d%lf",&T,&Tg,&k);

        double s=1.0*dis[n]/k;

        if(Tg-s-T>0.001)

        printf("Good job,KK!\n");

        else

        printf("What a pity!\n");

    }

    return 0;

}