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[],h,t,vis[],p[],ans=2e9,f[];
vector <pair<int,int> >a[];
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,,sizeof(vis));
memset(f,,sizeof(f));
h=t=;
l[++t]=,f[]=p[];
vis[]=;
while(h<t){
h+=;
int front=l[h];vis[front]=;
for(int i=;i<a[front].size();i++){
int to=a[front][i].first;
if(p[to]+max(,f[front]-a[front][i].second)<f[to]&&p[to]+max(,f[front]-a[front][i].second)<=wks){
f[to]=p[to]+max(,f[front]-a[front][i].second);
if(!vis[to])vis[to]=,l[t=t+]=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=;i<=n;i++)scanf("%d",&p[i]);
for(int i=;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[],r=;
while(l<r){
int mid=(l+r)>>;
if(!SPFA(mid))l=mid+;
else r=mid;
}
printf("%d",l);
fclose(stdin),fclose(stdout);
return ;
}