ROADS POJ - 1724 约束最短路 暴搜 加剪枝

http://poj.org/problem?id=1724

题意：最短路的模板，不过每条边加上一个费用，要求总费用不超过k

题解：不能用dijkstra ，直接暴力，dfs维护len和cost。

　　　　普通的剪枝：如果当前的cost大于k直接跳出，如果当前的len大于minlen(目前的最优解），跳出。

　　　　另一个剪枝：维护花费一定费用 到达某个点 的最短路minL[v][cost]，如果当前的len大于L，则跳出。

ac代码：

#define _CRT_SECURE_NO_WARNINGS

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<cmath>

#include<cstdio>

#include<string>

#include<stack>

#include<ctime>

#include<list>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<sstream>

#include<iostream>

#include<functional>

#include<algorithm>

#include<memory.h>

//#define INF 0x3f3f3f3f

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

#define rep(i,t,n)  for(int i =(t);i<=(n);++i)

#define per(i,n,t)  for(int i =(n);i>=(t);--i)

#define mp make_pair

#define pb push_back

#define mmm(a,b) memset(a,b,sizeof(a))

//std::ios::sync_with_stdio(false);

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

void smain();

#define ONLINE_JUDGE

int main() {

    ios::sync_with_stdio(false);

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

    long _begin_time = clock();

#endif

    smain();

#ifndef ONLINE_JUDGE

    long _end_time = clock();

    printf("time = %ld ms.", _end_time - _begin_time);

#endif

    return ;

}

const int maxn = 1e4 + ;

const ll mod = 1e5 + ;

const ll INF = ()*(200000ll) + ;

ll n, d;

ll k, r, s,  l, t;

int minlen;

int cost, len;

int vis[];

int minL[][maxn];

ll a[maxn];

struct road {

    int d, L, t;

};

vector<vector<road> >citymap();

//vector<int> a[maxn];

void Run() {

}

void dfs(int s) {

    if (s == n) { minlen = min(minlen, len); return;}

    rep(i, , citymap[s].size() - ) {

        road now = citymap[s][i];

        if (vis[now.d])continue;

        if (cost + now.t > k)continue;

        if (len + now.L >= minlen)continue;

        if (minL[now.d][cost+now.t] <= len + now.L)continue;

        len += now.L;

        cost += now.t;

        minL[now.d][cost] = len;

        vis[now.d] = ;

        dfs(now.d);

        vis[now.d] = ;

        len -= now.L;

        cost -= now.t;

    }

}

void smain() {

    cin >> k >> n >> r;

    rep(i, , r) {

        road R;

        int s;

        cin >> s >> R.d >> R.L >> R.t;

        if (s != R.d)citymap[s].push_back(R);

    }

    rep(i,,)

        rep(j, , maxn - ) {

        minL[i][j] =  << ;

    }

    memset(vis, , sizeof(vis));

    len = , cost = ;

    vis[] = ;

    minlen = ( << );

    dfs();

    minlen <  <<  ? cout << minlen : cout << -;

}