sdutacm-最短路径

最短路径

Time Limit: 1000MS MemoryLimit: 65536KB

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 1

0 1 1

0 1 2

3 2

0 1 1

1 2 1

0 2 2

ExampleOutput

No Answer!

Hint

Author

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

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define inf 999999999999
struct 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: Accepted
Take time: 28ms
Take Memory: 880KB
Submit time: 2017-02-16 21:34:33
****************************************************/