sdutacm-最短路径

最短路径

Time Limit: 1000MS MemoryLimit: 65536KB

SubmitStatistic

PRoblemDescription

为了准备一年一度的校赛，大家都在忙着往赛场搬运东西，比如气球什么的。这时 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的倍数，输出“NoAnswer!”(不包含引号)。

注意：64-bit整型请使用 long long来定义，并且使用 %lld或 cin、cout来输入输出，请不要使用__int64和 %I64d。

ExampleInput

2

2 1

0 1 1

0 1 2

3 2

0 1 1

1 2 1

0 2 2

ExampleOutput

No Answer!

2

Hint

Author

 “师创杯”山东理工大学第五届ACM程序设计竞赛

#include <iostream>#include<bits/stdc++.h>using namespace std;#define inf 999999999999struct node{    int u,v;    long long w;    int next;}eage[4000010];int vis[500010],head[500010];long long dis[555][12];int cnt,n,m;void add(int u,int v, long long w){    eage[cnt].u = u;    eage[cnt].v = v;    eage[cnt].w = w;    eage[cnt].next = head[u];    head[u] = cnt++;}void spfa(int s,int e,int x){   int i;    queue<int>q;    while(!q.empty())q.pop();    //memset(vis,0,sizeof(vis));    for(i=0;i<=n;i++)    {        vis[i] = 0;        for(int j=0;j<=x;j++)        {        dis[i][j] = inf;        }    }    dis[s][0] = 0;//表示到点s到某点的最短路径数组    vis[s] = 1;//表示该点是否已经在队列中    q.push(s);    while(!q.empty())    {        int u = q.front();        q.pop();        vis[u] = 0;        for(i=head[u];i!=-1;i = eage[i].next)        {            int v = eage[i].v;            int w = eage[i].w;            for(int j=0;j<x;j++)            {                if(dis[u][j]<inf&&dis[v][(j+1)%x]>dis[u][j]+w)                {                    dis[v][(j+1)%x] =dis[u][j]+w;                    if(!vis[v])                    {                        vis[v] = 1;                        q.push(v);                    }                }            }        }    }    if(dis[e][0]==inf)printf("No Answer!/n");    else printf("%lld/n",dis[e][0]);}int main(){    int m,v,s,e,u,x;    long long w;    int t;    scanf("%d",&t);    while(t--)    {    scanf("%d %d",&n,&m);        memset(head,-1,sizeof(head));        cnt = 0;        while(m--)        {            scanf("%d%d%lld",&u,&v,&w);            add(u,v,w);        }        scanf("%d%d%d",&s,&e,&x);        spfa(s,e,x);       // printf("%d/n",dis[e]);    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 28msTake Memory: 880KBSubmit time: 2017-02-16 21:34:33****************************************************/