ZOJ 3524 Crazy Shopping

Crazy Shopping

Time Limit: 3ms
Memory Limit: 65536KB
This problem will be judged on ZJU. Original ID: 3524
64-bit integer IO format: %lld      Java class name: Main

Because of the 90th anniversary of the Coherent & Cute Patchouli (C.C.P), Kawashiro Nitori decides to buy a lot of rare things to celebrate.

 

ZOJ 3524 Crazy Shopping

 

Kawashiro Nitori is a very shy kappa (a type of water sprite that live in rivers) and she lives on Youkai MountainYoukai Mountain is a dangerous place full of Youkai, so normally humans are unable to be close to the mountain. But because of the financial crisis, something have changed. For example, Youkai Mountainbecomes available for tourists.

On the mountain there are N tourist attractions, and there is a shop in each tourist attraction. To make the tourists feel more challenging (for example, to collect all kinds of souvenirs), each shop sells only one specific kind of souvenir that can not buy in any other shops. Meanwhile, the number of the souvenirs which sells in each shop is infinite. Nitori also knows that each kind of souvenir has a weight TWi (in kilogram) and a valueTVi.

Now Nitori is ready to buy souvenirs. For convenience, Nitori numbered the tourist attraction from 1 to N. At the beginning Nitori is located at the tourist attraction X and there are M roads connect some pairs of tourist attractions, and each road has a length L. However, because Youkai Mountain is very steep, all roads are uni-directional. By the way, for same strange reason, the roads ensure that when someone left one tourist attraction, he can not arrive at the same tourist attraction again if he goes along the road.

Nitori has one bag and the maximal load is W kilogram. When there are K kilogram things in Nitori's bag, she needs to cost K units energy for walking one unit length road. Of course she doesn't want to waste too much energy, so please calculate the minimal cost of energy of Nitori when the value is maximal.

Notice: Nitori can buy souvenir at tourist attraction X, and she can stop at any tourist attraction. Also, there are no two different roads between the same two tourist attractions. Moreover, though the shop sells different souvenirs, it is still possible for two different kinds of souvenir have the same weight or value.

Input

There are multiple test cases. For each test case:

The first line contains four numbers N (1 <= N <= 600) - the number of tourist attractions, M (1 <= M <= 60) - the number of roads, W (1 <= W <= 2) - the load of the bag and X (1 <= X <= N) - the starting point ofNitori.

Then followed by N lines, each line contains two integers which means the shop on tourist attraction i sells theTWi and TVi things (1 <= TWi <= W, 1 <= TVi <= 10).

Next, there are M lines, each line contains three numbers, XiYi and Li, which means there is a one-way road from tourist attraction Xi to Yi, and the length is Li (1 <= Xi,Yi <= N, 1 <= Li <= 10).

Output

For each test case, output the answer as the description required.

Sample Input

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

Sample Output

0

Hint

It's no hard to know that Nitori can buy all things at tourist attraction 2, so she cost 0 unit energy.

 

Author

DAI, Longao
 
解题:。。拓扑排序后进行完全背包。。。
 
ZOJ 3524 Crazy Shopping
ZOJ 3524 Crazy Shopping
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 700;
  4 struct arc {
  5     int to,w,next;
  6     arc(int x = 0,int y = 0,int z = -1) {
  7         to = x;
  8         w = y;
  9         next = z;
 10     }
 11 } e[120];
 12 int head[maxn],ind[maxn],tot,n,m,w,x;
 13 int dp[maxn][2006],energy[maxn][2006];
 14 int cw[maxn],cv[maxn];
 15 bool done[maxn];
 16 vector<int>sorted;
 17 queue<int>q;
 18 void add(int u,int v,int w) {
 19     e[tot] = arc(v,w,head[u]);
 20     head[u] = tot++;
 21 }
 22 void topSort() {
 23     while(!q.empty()) q.pop();
 24     for(int i = 1; i <= n; ++i)
 25         if(!ind[i]) q.push(i);
 26     while(!q.empty()) {
 27         int u = q.front();
 28         q.pop();
 29         sorted.push_back(u);
 30         for(int i = head[u]; ~i; i = e[i].next)
 31             if(--ind[e[i].to] == 0) q.push(e[i].to);
 32     }
 33 }
 34 void solve() {
 35     for(int i = 0; i <= w; ++i) {
 36         energy[x][i] = 0;
 37         if(i >= cw[x])
 38             dp[x][i] = max(dp[x][i],dp[x][i - cw[x]] + cv[x]);
 39     }
 40     int maxV = dp[x][w],minW = 0;
 41     done[x] = true;
 42 
 43     for(int i = 0; i < sorted.size(); ++i) {
 44         if(!done[sorted[i]]) continue;
 45         int u = sorted[i];
 46 
 47         for(int j = head[u]; ~j; j = e[j].next) {
 48             int v = e[j].to;
 49             done[v] = true;
 50             for(int k = 0; k <= w; ++k) {
 51                 if(dp[v][k] < dp[u][k]) {
 52                     dp[v][k] = dp[u][k];
 53                     energy[v][k] = energy[u][k] + e[j].w*k;
 54                 } else if(dp[v][k] == dp[u][k]){
 55                     if(energy[v][k] == -1) energy[v][k] = energy[u][k] + e[j].w*k;
 56                     else energy[v][k] = min(energy[v][k],energy[u][k] + e[j].w*k);
 57                 }
 58             }
 59 
 60             for(int k = cw[v]; k <= w; ++k)
 61             if(dp[v][k] < dp[v][k - cw[v]] + cv[v]){
 62                 dp[v][k] = dp[v][k - cw[v]] + cv[v];
 63                 energy[v][k] = energy[v][k - cw[v]];
 64             }else if(dp[v][k] == dp[v][k - cw[v]] + cv[v])
 65                 energy[v][k] = min(energy[v][k],energy[v][k - cw[v]]);
 66 
 67             for(int k = 0; k <= w; ++k)
 68             if(dp[v][k] > maxV  dp[v][k] == maxV && energy[v][k] < minW){
 69                 maxV = dp[v][k];
 70                 minW = energy[v][k];
 71             }
 72         }
 73     }
 74     printf("%d\n",minW);
 75 }
 76 int main() {
 77     int u,v,c;
 78     while(~scanf("%d %d %d %d",&n,&m,&w,&x)) {
 79         memset(head,-1,sizeof head);
 80         memset(ind,0,sizeof ind);
 81         memset(done,false,sizeof done);
 82         sorted.clear();
 83         memset(energy,-1,sizeof energy);
 84         memset(dp,0,sizeof dp);
 85         for(int i = 1; i <= n; ++i)
 86             scanf("%d %d",cw+i,cv+i);
 87         for(int i = tot = 0; i < m; ++i) {
 88             scanf("%d %d %d",&u,&v,&c);
 89             ++ind[v];
 90             add(u,v,c);
 91         }
 92         topSort();
 93         solve();
 94     }
 95     return 0;
 96 }
 97 /*
 98 4 4 10 1
 99 3 5
100 2 2
101 3 3
102 1 1
103 1 2 5
104 1 3 10
105 2 4 4
106 3 4 5
107 */
View Code

 

更多相关文章
  • http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4439 题意: n个点的有向无环图,边有长度,从一个点到另一点消耗背包重量与边长的乘积.每个点卖物品,价值v,重量w,数量无限,给定起点,和背包容量,可以在任意点停止,问最大化所获
  • Crazy Shopping(拓撲排序+完全背包)
    Crazy Shopping(拓扑排序+完全背包) Because of the 90th
  • In the past twenty years, China has faced three American presidents, but till coming to Yale today, I never realized that China really just faced one ...
  •         这阵子都没怎么写代码,由于开学,忙于各种琐碎的事情,现在静下来了开始跟着暑假的节奏刷题了.         这道题一开是没看清题目-在寝室刷题就是效率不高...         后来才知道,题目意思是,一个环形序列,1minute可以交换相邻的两个位置,问逆序所需的最小时间是多少. ...
  • 转自——http://blog.csdn.net/qwe20060514/article/details/8112550   =============================以下是最小生成树+并查集======================================[HDU]121
  • ZOJ Monthly, October 2015 K题 二分答案+验证 #include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<m ...
  • ZOJ 3406 Another Very Easy Task #include <cstdio> #include <cstring> const int N = 105; char s[N]; int main() { bool f = 0; int size = 0; ...
  • BCD CodeTime Limit: 5 Seconds      Memory Limit: 65536 KB Binary-coded decimal (BCD) is an encoding for decimal numbers in which each digit is represe
一周排行