最短路径

客官°小女子只卖身不卖艺 2022-07-12 08:26 217阅读 0赞

#### 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≤230），代表有一条从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 ####

2
    2 1
    0 1 1
    0 1 2
    3 2
    0 1 1
    1 2 1
    0 2 2

#### Example Output ####

No Answer!
    2

SPFA算法：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define maxn 10010
    const 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;
    }