最短路径

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;}