最短路径

比眉伴天荒 2022-08-18 02:28 181阅读 0赞

## 最短路径 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

YY 并不是把东西直接搬到赛场，而是从S 路口搬运到T 路口。由于YY 非常懒而且他有轻度强迫症。所以他要走的路需要尽可能的短，并且走过路径的数目要为X 的倍数。

## 输入 ##

≤≤对于每组测试数据：

≤≤≤≤接下来V、, , 0≤W≤2），代表有一条从V的长度为最后一行为三个正整数T 、≤, N≤10）。

## 输出 ##

“)。

64-bit 整型请使用long long 来定义，并且使用%lld 或cin、<font new="" roman,="" serif\\"="" face="\\"Times">%I64d。

## 示例输入 ##

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

## 示例输出 ##

No Answer!
    2

## 提示 ##

## 来源 ##

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

## 示例程序 ##

#include <stdio.h>  
    #include <string.h>  
    #include <queue>  
    #include <climits>  
    using namespace std;  
     long long INF=LONG_LONG_MAX;  
     long long dis[110][12];  
    int vis[110];  
    struct edge  
    {  
        int to;  
        int w;  
    };  
    int n,m,s,t,x;  
    vector<struct edge>map[110];  
    void SPFA()  
    {  
        queue<int>a;  
        for(int i=0; i<n; i++)  
        {  
            for(int k=0; k<=x; k++)  
            {  
                dis[i][k]=INF;  
            }  
        }  
        memset(vis,0,sizeof(vis));  
        dis[s][0]=0;  
        vis[s]=1;  
        a.push(s);  
        while(!a.empty())  
        {  
            int u=a.front();  
            a.pop();  
            vis[u]=0;  
            int tt=map[u].size();  
            for(int i=0; i<tt; i++)  
            {  
                int to=map[u][i].to;  
                for(int j=0; j<x; j++)  
                {  
                    if(dis[u][j]<INF&&dis[to][(j+1)%x]>dis[u][j]+map[u][i].w)  
                    {  
                        dis[to][(j+1)%x]=dis[u][j]+map[u][i].w;  
                        if(!vis[to])  
                        {  
                            a.push(to);  
                            vis[to]=1;  
                        }  
                    }  
                }  
            }  
        }  
    }  
    int main()  
    {  
        int T,u,v,w;  
        struct edge tmp;  
        scanf("%d",&T);  
        while(T--)  
        {  
            scanf("%d %d",&n,&m);  
            for(int i=0; i<n; i++)  
            {  
                map[i].clear();  
            }  
            for(int i=1; i<=m; i++)  
            {  
                scanf("%d %d %d",&u,&v,&w);  
                tmp.to=v;  
                tmp.w=w;  
                map[u].push_back(tmp);  
            }  
            scanf("%d %d %d",&s,&t,&x);  
            SPFA();  
            if(dis[t][0]>=INF)  
            {  
                printf("No Answer!\n");  
            }  
            else  
            {  
                printf("%lld\n",dis[t][0]);  
            }  
        }  
        return 0;  
    }