首页 > 搜索 > DFS搜索 > HDU 3021-Tree Fence-动态规划-[解题报告]HOJ
2014
02-27

HDU 3021-Tree Fence-动态规划-[解题报告]HOJ

Tree Fence

问题描述 :

XEN has a small yard. The yard is square and 1000*1000 large. The lower left corner has coordinates (0, 0), the upper right (1000, 1000). There are N trees in the yard. In order to protect them, XEN wants to fence some of them.

XEN can only select some of the M positions which are provided in advance to insert wood piles, then he built fence along the inserted wood piles. Finally, the fence will be a polygon. As the picture below (Data is in the Sample):

 FunnyXEN

XEN should pay 47 yuan for each wood pile which were inserted. But he can get 173 yuan from each tree which is in the final polygon. Obviously,the income is the difference between the total money he get and the total money he pay.

Now XEN want to know the maximum income he will get. But he doesn’t know how to calculate it so that he asks your perfect team for help. Can you help him?

输入:

Your program is to read from standard input.

In the first line, there are two integer N, M (1 ≤ N, M ≤ 200), as the description means. The following lines are in the format: the former N lines are the locations of trees, the other M lines are for the M positions. In addition, there is a space between the two numbers of the same line.

Tx1 Ty1
Tx2 Ty2

Txn Tyn
Px1 Py1
Px2 Py2

PXm Pym

(0 ≤ Txi, Tyi, Pxi, Pyi ≤ 1000, Integer!)

输出:

Your program is to read from standard input.

In the first line, there are two integer N, M (1 ≤ N, M ≤ 200), as the description means. The following lines are in the format: the former N lines are the locations of trees, the other M lines are for the M positions. In addition, there is a space between the two numbers of the same line.

Tx1 Ty1
Tx2 Ty2

Txn Tyn
Px1 Py1
Px2 Py2

PXm Pym

(0 ≤ Txi, Tyi, Pxi, Pyi ≤ 1000, Integer!)

样例输入:

3 4
400 300
600 500
800 900
800 300
200 200
200 700
600 700

样例输出:

205


Go Home


Time limit: 1sec. Submitted: 60
Memory limit: 64M Accepted: 37
Source: HIT ACM/ICPC Group

When every holidays coming, students in HIT are filled with desire to go back home. Aragron is one of these students who wants to go home as quickly as possible.

Now Aragron has known some ways to travel to some other cities, and he only has limited money C. Aragron wants to know the least time he needed to go back home by using a limited money C. Can you help him?

Input

The input begins with a single positive integer on a line indicating the number of the cases following.

The first line of each case contains three integers N, M, C, means a undirected graph consist of N (2 <= N <= 500) nodes, M(N <= M <= 1000) edges and the limited money C(1 <= C <= 500).

The next M lines contains four integers u, v, c, and t for each line. u, v(1 <= u, v <= n) means the two nodes connected by edge. c(1 <= c <= 80) means Aragron needs to cost c money to go through the edge. t(1 <= t <= 100) means Aragron needs to use t time to go through the edge.

HIT is always in the node 1, and Aragron’s home is always in the node n. It is guaranteed that it has at least one road connect HIT and Aragron’s home.

Output

For each case, output one integer: The least time Aragron needs to go home with the sum of costs do not exceed the limited money C, or “-1” if Aragron can not get home with the limited money C.

Sample Input

2 3 3 3 1 3 5 2  3 2 2 5 2 1 2 4 5 10 5 1 2 2 10 1 3 2 5 1 4 2 15 1 5 10 1 2 3 2 5 2 4 2 10 2 5 3 15 3 4 1 2 3 5 3 10 4 5 2 2 

Sample Output

-1 9
题目大意:求从1到n花费不超过C时间不超过T 所得的最小花费
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#define MIN(a,b) a>b?b:a
#define MAX 2000000000
using namespace std;
int N, edge, C, fro, to, ci, ti;
long RES;
int map[501][501];
int c[501][501];
int t[501][501];
int used[501];
void dfs(int i, int j, int T) {
    int k, l;
    if (i == N) {
        RES = MIN(RES, T);
        return;
    }
    if (used[i] == 0) {
        used[i] = 1;
        for (k = 1; k <= map[i][0]; k++) {
            if (j + c[i][map[i][k]] <= C && T + t[i][map[i][k]] < RES)
                dfs(map[i][k], j + c[i][map[i][k]], T + t[i][map[i][k]]);
        }
        used[i] = 0;
    }
}
int main() {
    int CAS;
    scanf(“%d”, &CAS);
    while (CAS–) {
        memset(map, 0, sizeof (map));
        memset(used, 0, sizeof (used));
        RES = MAX;
        scanf(“%d %d %d”, &N, &edge, &C);
        for (int i = 0; i < edge; i++) {
            scanf(“%d %d %d %d”, &fro, &to, &ci, &ti);
            map[fro][++map[fro][0]] = to;
            map[to][++map[to][0]] = fro;
            c[fro][to] = c[to][fro] = ci;
            t[fro][to] = t[to][fro] = ti;
        }
        dfs(1, 0, 0);
        if (RES == MAX) printf(“-1\n”);
        else printf(“%ld\n”, RES);
    }
    return 0;
}
参考:http://zhulinb123.blog.163.com/blog/static/184414043201143111654536/