WILL 吃桃
(peach.pas/c/cpp)
【 题目描述】
Will 很喜欢吃桃， 某天 Will 来到了一片森林， 森林中有 N 颗桃树， 依次编号为 1,2,„,N.每棵树上有数量不等的桃子。 某些桃树之间有单向通行的小路， 且路径不会形成环， 通过每条小路的时间也不一定相同。 现在， Will 提着一个最多可以容纳 K 个桃子的篮子， 从编号为1 的桃树出发， 走过若干条小路之后来到编号为 N 的桃树。 当 Will 在路上走的时候， 每走 1分钟， 他会从篮子中拿出一个桃子来吃掉（ 如果篮子中还有桃子的话， 如果篮子中没有桃子的话那就没得吃了！）。 每到一棵桃树（ 包括起点和终点）， 他会把这棵桃树上的所有桃子摘下来放入篮子中。 现在你的问题是： 求 K 的最小值， 使得 Will 能够不浪费任何桃子（ 每到一棵桃树， 这棵树上的所有桃子都必须被装入篮子中）。
【 输入格式】
输入文件第一行两个整数， N,m， 分别表示桃树的数量以及连接桃树的小路的数量。
接下来一行 N 个用空格隔开的整数， 分别表示每一颗桃树上的桃子的数量。
接下来 m 行， 每行 3 个用空格隔开的整数， a,b,c， 表示有一条小路能够从桃树 a 走到桃树 b，（ 注意小路一定是单向的）， 走过这条小路所需要的时间是 c 分钟。从任意一棵桃树出发， Will 不可能沿着小路走若干条路之后重新回到这棵桃树。（ 给出的图是一个有向无环图。） 数据保证 Will 一定能够从桃树 1 走到桃树 N。
【 输出格式】
输出文件有且仅有一行， 一个整数， 表示 K 的最小值
【 输入样例】
3 3
5 1 6
1 3 1
1 2 4
2 3 5
【 输出样例】
6
【 数据规模】
对于 30%的数据： 3≤N≤10； m≤20；
对于 60%的数据： 3≤N≤1,000； m≤10,000；
对于 100%的数据： 3≤N≤10,000； 3≤m≤30,000； 所有其他数据都不超过 10000；
乍一看，数据很大，所以在这儿我们可以二分答案，SPFA判断是否可行。
code：
#include <cstdio> #include <vector> #include <cstring> #define mm 120000 using namespace std; int n,m,l[120001],h,t,vis[10001],p[10001],ans=2e9,f[10001]; vector <pair<int,int> >a[10001]; inline int min(int x,int y){return x<y?x:y;} inline int max(int x,int y){return x>y?x:y;} int SPFA(int wks){ memset(vis,0,sizeof(vis)); memset(f,63,sizeof(f)); h=t=0; l[++t]=1,f[1]=p[1]; vis[1]=1; while(h<t){ h+=1; int front=l[h];vis[front]=0; for(int i=0;i<a[front].size();i++){ int to=a[front][i].first; if(p[to]+max(0,f[front]-a[front][i].second)<f[to]&&p[to]+max(0,f[front]-a[front][i].second)<=wks){ f[to]=p[to]+max(0,f[front]-a[front][i].second); if(!vis[to])vis[to]=1,l[t=t+1]=to; } } } return f[n]<=wks; } int main(){ freopen("peach.in","r",stdin); freopen("peach.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&p[i]); for(int i=1;i<=m;i++){ int x,y,c;scanf("%d%d%d",&x,&y,&c); a[x].push_back(make_pair(y,c)); } int l=p[1],r=100000005; while(l<r){ int mid=(l+r)>>1; if(!SPFA(mid))l=mid+1; else r=mid; } printf("%d",l); fclose(stdin),fclose(stdout); return 0; }