2018.7.16 题解 2018暑假集训之Roads-roads

题面描述###

有标号为1……n的城市与单行道相连。对于每条道路有两个与之相关的参数：道路的长度以及需要支付的费用（用硬币的数量表示）

鲍勃和爱丽丝曾经生活在城市1。在注意到爱丽丝在他们喜欢玩的卡牌游戏中作弊后，鲍勃决定与爱丽丝分手并搬走——去城市n。他希望尽快到达那里——越快越好，然而他现在有些现金短缺。我们希望帮助鲍勃找到从城市1到城市n的一条最短路径——但他必须用他现有的钱支付得起。

输入输出格式###

输入格式###

输入的第一行含有一个整数t代表测试样例的组数。下面是t组测试样例。

对于每组测试数据，第一行含有一个整数K（0<=K<=10000)，代表鲍勃所能支付得起的最大费用。

第二行含有一个整数N（2<=N<=100)，代表城市总数。

第三行含有一个整数R（1<=R<=10000)，代表道路的总数。

接下来R行每行用四个整数S,D,L,T，以单个空格分隔：

S表示出发点城市标号（1<=S<=N)；

D表示目的地城市标号（1<=D<=N)；

L是该道路的长度（1<=L<=100)； T表示经过该道路的费用(0<=T<=100)。

注意不同的道路可能拥有相同的起点和终点。

输出格式###

对于每组测试样例，输出单独的一行表示当花费小于等于K时最短路径的长度。如果不存在这样的路径，输出-1。

一道dfs+邻接表存图……

其实就是一道带有限制的dfs

上代码带注释

#include <cstdio>

#include <cstring>

#include <iostream>

#define mem(a,b) memset(a,b,sizeof(a))//数组初始化

#define inf 0x3f3f3f3f

#define N 100+20

#define M 1000000+10

#define ll long long

using namespace std;

int first[N],vis[N],t;

int k,n,m,len,sum;

struct node//存边

{

    int u,v,w,cost;//编号，左节点,花费

    int next;//下一条边

}g[10200];

void add_edge(int,int,int,int);//建边

void dfs(int,int,int);//搜索

int main()

{

    scanf("%d",&t);

    while(t--)

    {

     int a,b,c,d;

     len=0,sum=0;

     mem(vis,0);

     mem(first,-1);

     scanf("%d%d%d",&k,&n,&m);

     for(int i=0; i<m; i++)

     {

         scanf("%d%d%d%d",&a,&b,&c,&d);

         add_edge(a,b,c,d);

     }

     sum=inf;

     dfs(1,0,0);

     if(sum==inf)

         puts("-1");

     else

         printf("%d\n",sum);

 }

    return 0;

}

void add_edge(int u,int v,int w,int cost)

{

    g[len].v=v;

    g[len].w=w;

    g[len].cost=cost;

    g[len].next=first[u];

    first[u]=len++;

}

void dfs(int x,int step,int cost)

{

    if(cost>k||step>sum)//剪枝：花费大于要求或长度大于已知

        return;

    if(x==n)

        sum=min(sum,step);//回溯

    for(int i=first[x]; i!=-1; i=g[i].next)//邻接表遍历

    {

        int v=g[i].v;

        if(!vis[v])

        {

            vis[v]=1;

            dfs(v,step+g[i].w,cost+g[i].cost);//下一步

            vis[v]=0;//回溯

        }

    }

}

巴特西