Escape Time II(DFS 검색)

Escape Time II
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu
Submit 
Status 
Practice 
ZOJ 3620
Description
There is a fire in LTR ’ s home again. The fire can destroy all the things in t seconds, so LTR has to escape in t seconds. But there are some jewels in LTR ’ s rooms, LTR love jewels very much so he wants to take his jewels as many as possible before he goes to the exit. Assume that the ith room has ji jewels. At the beginning LTR is in room s, and the exit is in room e.
Your job is to find a way that LTR can go to the exit in time and take his jewels as many as possible.
Input
There are multiple test cases.  For each test case:  The 1st line contains 3 integers n (2 ≤ n ≤ 10), m, t (1 ≤ t ≤ 1000000) indicating the number of rooms, the number of edges between rooms and the escape time. The 2nd line contains 2 integers s and e, indicating the starting room and the exit. The 3rd line contains n integers, the ith interger ji (1 ≤ ji ≤ 1000000) indicating the number of jewels in the ith room. The next m lines, every line contains 3 integers a, b, c, indicating that there is a way between room a and room b and it will take c (1 ≤ c ≤t) seconds. 
Output
For each test cases, you should print one line contains one integer the maximum number of jewels that LTR can take. If LTR can not reach the exit in time then output 0 instead.
Sample Input

3 3 5
0 2
10 10 10
0 1 1 
0 2 2
1 2 3
5 7 9
0 3
10 20 20 30 20
0 1 2
1 3 5
0 3 3
2 3 2
1 2 5
1 4 4
3 4 2

Sample Output

30
80

이것은 DFS로 쉽게 해결할 수 있는 검색 문제임이 분명하다.프로그램의 모형은 매우 빨리 만들어졌지만, 많은 세부 문제에 주의하지 않아서, 결과적으로 WA는 몇 번이나 만들어졌다. T.T
요약하여 경험을 남기다.
1. 처음에 나는 경로가 아니라 정점을 표시했지만 이 문제는 링의 존재를 허락했다. 예를 들어 A-B-A, 정점을 표시하면 A에서 B로 가면 안 된다.그래서 경로를 표시합니다. A에서 B로 갈 때 경로를 표시합니다. 를 표시하는 것은 같은 경로를 반복하지 않기 위해서입니다. 왜 피해야 합니까?분명히 다시 를 걸을 때 Jewel을 수확할 수 없고 시간도 소모됩니다.
2. 정점은 표시할 필요가 없지만 이미 검색한 정점에 대해 포함된 jewel 수를 0까지 제거합니다.처음부터 나는 이 점을 알아차리지 못했다.
3. 현장을 복구하는 일은 잘 해야 한다.
4. e에 도착하면 바로 멈출 수 없습니다. 만약에 이때 총 시간이 규정된 시간 t를 초과하지 않으면 다른 정점을 검색하여 더 많은 jewel을 얻을 수 있습니다. 그러나 최종적으로 반드시 다시 e로 돌아가야 합니다. e에 도착할 때마다 jewel의 최대 수량을 업데이트해야 합니다.
AC code:

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;

int n, m, t, s, e;
int jew[10], cost[10][10], maxjew;
bool vis[10][10];

//r:room, sj:sum of jewels, st:sum of time
void DFS(int r, int sj, int st)
{
    if(r == e && sj > maxjew)
        maxjew = sj;
    for(int i = 0; i < n; i++)
    {
        if(!vis[r][i] && cost[r][i] && r != i && st + cost[r][i] <= t)
        {
            // jew[i] 0, 
            int val = jew[i];
            jew[i] = 0;
            // vis[r][i]=vis[i][r]=1, ， A-B-A， 
            // A B B A ， B e（ A e）
            vis[r][i] = 1;
            DFS(i, sj + val, st + cost[r][i]);
            vis[r][i] = 0;
            jew[i] = val;
        }
    }
    return ;
}

int main()
{
    while(scanf("%d %d %d", &n, &m, &t) != EOF)
    {
        // 
        memset(cost, 0, sizeof(cost));
        memset(vis, 0, sizeof(vis));
        maxjew = 0;
        // 
        scanf("%d %d", &s, &e);
        for(int i = 0; i < n; i++)
            scanf("%d", &jew[i]);
        for(int j = 0, a, b; j < m ;j++)
        {
            scanf("%d %d", &a, &b);
            scanf("%d", &cost[a][b]);
            cost[b][a] = cost[a][b];
        }
        //dfs
        int val = jew[s];
        jew[s] = 0; //s jewel 
        DFS(s, val, 0);
        // 
        printf("%d
", maxjew);
    }
    return 0;
}