USACO18DEC Fine Dining G

P5122 [USACO18DEC] Fine Dining G

题目大意

有一个由$n$个点$m$条边构成的无向连通图，这$n$个点的编号为$1$到$n$。前$n-1$个点上都有一头奶牛，这些奶牛都要前往$n$号点。第$i$条边连接$a_i$和$b_i$，经过需要时间$t_i$。

有$k$个干草捆分布在这些点中，第$i$个干草捆的美味值为$y_i$。每头奶牛都希望能够在某一处干草捆处停留并吃草，但奶牛只会在经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值时这样做。一头奶牛只会在一处干草捆处停留并吃草。

输出有$n-1$行。如果第$i$个点的奶牛可以在回牛棚的路上会前往某一个干草捆并且在此进食，则第$i$行输出$1$；否则，输出$0$。

可能有多个干草捆在同一个点。

$2\le n\le 5\times 10^4,1\le m\le 10^5$

题解

用$\text{dijkstra}$算出第$n$个点到各个点的距离，设到第$i$个点的距离为$di{s}_i$。

将所有有干草捆的点$x$作为第二次$\text{dijkstra}$的起点，起始值设为$di{s}_x-y_x$，意为从点$x$到点$n$的距离减去这个干草捆的美味值。用这些点为起点做一次$\text{dijkstra}$，到各个点的距离记为$t{d}_i$。

最后，对于每个$1\le i<n$，如果$t{d}_i\le di{s}_i$，则可以在一个干草捆停留，否则不行。

时间复杂度为$O((n+m)\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,z,tot=0,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 x>ax.x;}
};
priority_queue<node>q;
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 i=1;i<=n;i++){vs[i]=0;dis[i]=2e9;}dis[n]=0;q.push((node){n,0});while(!q.empty()){int u=q.top().id;q.pop();if(vs[u]) continue;vs[u]=1;for(int i=r[u];i;i=l[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 i=1;i<=n;i++){vs[i]=0;if(td[i]<2e9) q.push((node){i,td[i]});}while(!q.empty()){int u=q.top().id;q.pop();if(vs[u]) continue;vs[u]=1;for(int i=r[u];i;i=l[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 i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dd1();for(int i=1;i<=n;i++) td[i]=2e9;for(int i=1;i<=k;i++){scanf("%d%d",&x,&z);td[x]=min(td[x],dis[x]-z);}dd2();for(int i=1;i<n;i++){if(td[i]<=dis[i]) printf("1\n");else printf("0\n");}return 0;
}