【2018.4.21】模拟賽之三-ssl2404 上學【深度優先搜尋】

正題

大意

有n個點，m輛車，每輛車有開車時間，需要走多久和需要多少錢。求在t個時間機關内到達可以需要花掉的最少價格

解題思路

暴力搜尋能過就對了

代碼

#include<cstdio>
#include<iostream>
using namespace std;
struct line{
    int next,to,st,ov,cost;
}a[];
int n,ls[],mins,xx,yy,sts,ovs,costs,m,mn,t;
bool walk[];
void add(int xx,int yy,int sts,int ovs,int costs)
{
    a[++m].next=ls[xx];
    a[m].to=yy;
    if (xx== && sts==) sts=;
    a[m].st=sts;
    a[m].ov=ovs;
    a[m].cost=costs;
    ls[xx]=m;
}//鄰接表加邊
void dfs(int x,int ans,int longg)
{
    //printf(" |%d(%d)(%d)| ",x,ans,longg);
    if (x==n && longg<=t) 
    {
        mins=min(mins,ans);//求最小值
        return;
    //  printf("*(%d)",ans);
    }
    walk[x]=true;//封路
    for (int q=ls[x];q;q=a[q].next)
    {
        if (!walk[a[q].to] && longg<a[q].st){
    //      printf("\n%d(>)\n",q);
            dfs(a[q].to,ans+a[q].cost,a[q].ov);//搜尋
    //      printf(" |%d| ",x);
        }
    }
    walk[x]=false;//回朔
    //printf("\n(<)\n");
}
int main()
{
    freopen("shaxu.in","r",stdin);
    freopen("shaxu.out","w",stdout);
    mins=;
    scanf("%d%d%d",&n,&t,&mn);
    for (int i=;i<=mn;i++)
    {
        scanf("%d%d%d%d%d",&xx,&yy,&sts,&ovs,&costs);
        add(xx+,yy+,sts,ovs,costs);
    }
    dfs(,,);
    if (mins!=) printf("%d",mins);
    else printf("-1");
}