wordpress目录分析,小小课堂seo自学网,在百度备案网站,福州门户网站P5122 [USACO18DEC] Fine Dining G
题目大意
有一个由 n n n个点 m m m条边构成的无向连通图#xff0c;这 n n n个点的编号为 1 1 1到 n n n。前 n − 1 n-1 n−1个点上都有一头奶牛#xff0c;这些奶牛都要前往 n n n号点。第 i i i条边连接 a i a_i ai和 b i b_i bi…P5122 [USACO18DEC] Fine Dining G
题目大意
有一个由 n n n个点 m m m条边构成的无向连通图这 n n n个点的编号为 1 1 1到 n n n。前 n − 1 n-1 n−1个点上都有一头奶牛这些奶牛都要前往 n n n号点。第 i i i条边连接 a i a_i ai和 b i b_i bi经过需要时间 t i t_i ti。
有 k k k个干草捆分布在这些点中第 i i i个干草捆的美味值为 y i y_i yi。每头奶牛都希望能够在某一处干草捆处停留并吃草但奶牛只会在经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值时这样做。一头奶牛只会在一处干草捆处停留并吃草。
输出有 n − 1 n-1 n−1行。如果第 i i i个点的奶牛可以在回牛棚的路上会前往某一个干草捆并且在此进食则第 i i i行输出 1 1 1否则输出 0 0 0。
可能有多个干草捆在同一个点。 2 ≤ n ≤ 5 × 1 0 4 , 1 ≤ m ≤ 1 0 5 2\leq n\leq5\times 10^4,1\leq m\leq 10^5 2≤n≤5×104,1≤m≤105 题解
用 dijkstra \text{dijkstra} dijkstra算出第 n n n个点到各个点的距离设到第 i i i个点的距离为 d i s i dis_i disi。
将所有有干草捆的点 x x x作为第二次 dijkstra \text{dijkstra} dijkstra的起点起始值设为 d i s x − y x dis_x-y_x disx−yx意为从点 x x x到点 n n n的距离减去这个干草捆的美味值。用这些点为起点做一次 dijkstra \text{dijkstra} dijkstra到各个点的距离记为 t d i td_i tdi。
最后对于每个 1 ≤ i n 1\leq in 1≤in如果 t d i ≤ d i s i td_i\leq dis_i tdi≤disi则可以在一个干草捆停留否则不行。
时间复杂度为 O ( ( n m ) log n ) O((nm)\log n) O((nm)logn)。
code
#includebits/stdc.h
using namespace std;
int n,m,k,x,y,z,tot0,d[200005],l[200005],r[200005],w[200005];
int vs[100005],dis[100005],td[100005];
struct node{int id,x;bool operator(const node ax)const{return xax.x;}
};
priority_queuenodeq;
void add(int xx,int yy,int zz){l[tot]r[xx];d[tot]yy;r[xx]tot;w[tot]zz;
}
void dd1(){for(int i1;in;i){vs[i]0;dis[i]2e9;}dis[n]0;q.push((node){n,0});while(!q.empty()){int uq.top().id;q.pop();if(vs[u]) continue;vs[u]1;for(int ir[u];i;il[i]){if(dis[d[i]]dis[u]w[i]){dis[d[i]]dis[u]w[i];q.push((node){d[i],dis[d[i]]});}}}
}
void dd2(){for(int i1;in;i){vs[i]0;if(td[i]2e9) q.push((node){i,td[i]});}while(!q.empty()){int uq.top().id;q.pop();if(vs[u]) continue;vs[u]1;for(int ir[u];i;il[i]){if(td[d[i]]td[u]w[i]){td[d[i]]td[u]w[i];q.push((node){d[i],td[d[i]]});}}}
}
int main()
{scanf(%d%d%d,n,m,k);for(int i1;im;i){scanf(%d%d%d,x,y,z);add(x,y,z);add(y,x,z);}dd1();for(int i1;in;i) td[i]2e9;for(int i1;ik;i){scanf(%d%d,x,z);td[x]min(td[x],dis[x]-z);}dd2();for(int i1;in;i){if(td[i]dis[i]) printf(1\n);else printf(0\n);}return 0;
}
