PRoblem Description

為了準備一年一度的校賽，大家都在忙著往賽場搬運東西，比如氣球什么的。這時YY 也沒有閑著，他也加入了搬運工的行列。已知學校有N 個路口和M 條路，YY并不是把東西直接搬到賽場，而是從S 路口搬運到T 路口。由于YY 非常懶而且他有輕度強迫癥。所以他要走的路需要盡可能的短，并且走過路徑的數目要為X 的倍數。

Input

輸入的第一行為一個正整數T(1≤ T≤ 20),代表測試數據組數。

對于每組測試數據：

輸入的第一行為兩個正整數N和M（1≤ N≤ 100, 1≤ M≤ 10000）。

接下來M行每行三個正整數U、V、W（0≤U,V<N, 0≤W≤2³⁰），代表有一條從U到V的長度為W的有向路徑。

最后一行為三個正整數S、T、X（0≤S,T< N, 1≤X ≤10）。

Output

對于每組測試數據，輸出滿足條件的從S 到T 的最短路徑。如果從S 到T 不可達，或者無法滿足路徑數是X 的倍數，輸出“No Answer!”(不包含引號)。

注意：64-bit整型請使用 long long來定義，并且使用 %lld或 cin、cout來輸入輸出，請不要使用 __int64和 %I64d。

Example Input

22 10 1 10 1 23 20 1 11 2 10 2 2
Example Output
No Answer!2
SPFA算法：
#include<stdio.h>#include<string.h>#include<stdlib.h>#define maxn 10010const long long max=9187201950435737471;struct node{    int u;    int v;    long long w;    int next;}map[maxn];int queue[maxn];long long dist[maxn][12];int book[maxn];int head[maxn];int front,rear,cnt,n;void add(int u,int v,long long w){    map[cnt].u=u;    map[cnt].v=v;    map[cnt].w=w;    map[cnt].next=head[u];    head[u]=cnt++;}void spfa(int s,int x){    int i,j,u,v;    long long w;    dist[s][0]=0;    book[s]=1;    rear=(rear+1)%maxn;    queue[rear]=s;    while(front!=rear)    {        front=(front+1)%maxn;        u=queue[front];        book[u]=0;        for(i=head[u];i!=-1;i=map[i].next)        {            v=map[i].v;            w=map[i].w;            for(j=0;j<x;j++)            {                if(dist[u][j]<max&&dist[v][(j+1)%x]>dist[u][j]+w)                {                    dist[v][(j+1)%x]=dist[u][j]+w;                    if(!book[v])                    {                        book[v]=1;                        rear=(rear+1)%maxn;                        queue[rear]=v;                    }                }            }        }    }}int main(){    int i,tt,m,u,v,s,t,x;    long long w;    scanf("%d",&tt);    while(tt--)    {        cnt=front=rear=0;        memset(head,-1,sizeof(head));        memset(book,0,sizeof(book));        memset(dist,max,sizeof(dist));        scanf("%d%d",&n,&m);        while(m--)        {            scanf("%d %d %lld",&u,&v,&w);            add(u,v,w);        }        scanf("%d%d%d",&s,&t,&x);        spfa(s,x);        if(dist[t][0]==max)        {            printf("No Answer!/n");        }        else        {            printf("%lld/n",dist[t][0]);        }    }    return 0;}