T4这道题考试时乍看不算太难，然而细考虑时，总在想若路径上有较小的环怎么搞，本就弱的代码实现能力再去实现错误的想法结果当然是瞎搞……

正解的方法真的是很巧妙，也是见的太少，想不到，但对我来说还是有些难理解…问了老师，自己又思考很久才想通……

在写注释时还是不太清楚，写完注释自己就比较清楚了（虽然旁人可能看不清楚XD）

对于算法，只是spfa，但不是单纯的点队列，而是对于每个点的每种%的情况的队列，话不多说，都在码里了

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>//d：与起点相连的边上最短边长度*2，即为起点直连的1个最小的环 
//此题主要在于，对于长度为p的1到n的路径，若其存在从1到n的一条路径l，l的长度%d=p%d且l的长度<=p 
using namespace std;
//因为只要有这样的l，p即为先在起点连接的最小的环绕((p-l)/d)圈再走l那条路径 
typedef pair<int,int> PR;
#define mp make_pair
#define fi first
#define sc second

const int N=10010,M=20010,inf=0x3f3f3f3f;
int n,m,Q,p,t,Head[N],ver[M],cost[M],Next[M],tot=1,mi=100,f[N][110],d;
bool vis[N][110];//f[i][j]：由起点1开始，到i点，长度%d==j的路径中，最短的路径的长度 
queue <PR> q;

void re(int &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}

inline void add(int x,int y,int z)
{
    ver[++tot]=y; cost[tot]=z; Next[tot]=Head[x]; Head[x]=tot;
}

void spfa(int mo)
{//不需要担心路径过程中更小的环，spfa过程中会一圈一圈套出来，最后求出的f[i][j]定为到i，距离%d为j的最短距离 
    int i,x,disx,y,disy;
    memset(f,0x3f,sizeof(f));//初始化为最大值，以便后期更新 
    q.push(mp(1,0)); vis[1][0]=1; f[1][0]=0;//到点1的距离当然为0，%d也为0，入队 
    while(!q.empty())
    {
        x=q.front().fi; disx=q.front().sc; q.pop();//取出队首，x为当前点，disx为当前到当前点的最小距离%d的值 
        for(i=Head[x];i;i=Next[i])
        {
            y=ver[i]; disy=(disx+cost[i])%mo;//y为下一点，disy为由当前点到y算出的1到y的距离%d的值 
            if(f[x][disx]+cost[i]<f[y][disy])//松弛操作 
            {
                f[y][disy]=f[x][disx]+cost[i];
                if(!vis[y][disy])//从1到y，路径长%d为disy的情况，没有再队列中 
                {
                    vis[y][disy]=1;
                    q.push(mp(y,disy));//入队 
                }
            }
        }
        vis[x][disx]=0;//退队 
    }
}

int main()
{
    int u,v,w,i;
    re(n); re(m);
    for(i=1;i<=m;i++)
    {
        re(u); re(v); re(w);
        add(u,v,w);
        add(v,u,w);//无向边建双向 
    }
    d=inf;
    for(i=Head[1];i;i=Next[i]) d=min(d,cost[i]);//找到起点1的出边中最短的 
    re(Q);
    if(d==inf)//如果起点1压根就没有出边，那肯定都不行 
    {
        while(Q--) printf("AKTang!\n");
        return 0;
    }
    d*=2;//把最短的出边*2，变成最小的环 
    spfa(d);//以最小的环为模数进行spfa 
    while(Q--)
    {
        re(p);
        if(f[n][p%d]<=p) printf("AWaDa!\n");//如果可以通过绕d跑几圈，加上一个路径到n，总长为p，存在总长为p的路径 
        else printf("AKTang!\n");//否则不存在 
    }
    return 0;
}