http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4744
Escape Time II
Time Limit: 2 Seconds Memory Limit: 65536 KB
There is a fire in LTR ’ s home again. The fire can destroy all the things in seconds, so LTR has to escape in 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 th room has jewels. At the beginning LTR is in room , and the exit is in room .
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 (2 ≤ ≤ 10), ,
(1 ≤ ≤ 1000000) indicating the number of rooms, the
number of edges between rooms and the escape time.
The 2nd line contains 2
integers and , indicating the starting room and the
exit.
The 3rd line contains integers, the th
interger (1 ≤ ≤ 1000000)
indicating the number of jewels in the th room.
The next
lines, every line contains 3 integers , ,
, indicating that there is a way between room and room
and it will take (1 ≤ ≤ )
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 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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxx = ;
int Edge[maxx][maxx];
int val[maxx];
bool vis[maxx];
int big = ,e,n,t;
void dfs(int s, int num,int ju)
{
if(num>t) return; if(s == e)
if(ju > big && num<=t)
big = ju; vis[s] = true;
for(int i=;i<n;i++)
{
if(i!=s && Edge[s][i]<1e8 && !vis[i])
{
dfs(i,num + Edge[s][i],ju + val[i]);
}
}
vis[s] = false; }
void Floyd()
{
for(int i=; i<n;i++)
for(int j=; j<n; j++)
for(int k=; k<n; k++)
if(Edge[j][i] + Edge[i][k] < Edge[j][k])
Edge[j][k] = Edge[j][i] + Edge[i][k];
}
int main()
{
int m;
int s;
while(~scanf("%d %d %d",&n,&m,&t))
{
memset(Edge,0x6,sizeof(Edge));
memset(val,,sizeof(val));
memset(vis,,sizeof(vis));
scanf("%d %d",&s,&e);
for(int i=;i<n;i++)
scanf("%d",&val[i]);
for(int i=;i<=m;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
Edge[u][v] = Edge[v][u] = w;
}
Floyd();
big = ;
vis[s] = true;
dfs(s,,val[s]);
printf("%d\n",big);
}
return ;
}