P5122 [USACO18DEC] Fine Dining G

題目大意

有一個由$n$個點$m$條邊構(gòu)成的無向連通圖，這$n$個點的編號為$1$到$n$。前$n?1$個點上都有一頭奶牛，這些奶牛都要前往$n$號點。第$i$條邊連接$a_i$和$b_i$，經(jīng)過需要時間$t_i$。

有$k$個干草捆分布在這些點中，第$i$個干草捆的美味值為$y_i$。每頭奶牛都希望能夠在某一處干草捆處停留并吃草，但奶牛只會在經(jīng)過這個干草捆使她回牛棚的時間增加不超過這個干草捆的美味值時這樣做。一頭奶牛只會在一處干草捆處停留并吃草。

輸出有$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)$。文章來源地址http://www.zghlxwxcb.cn/news/detail-665709.html

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;
}

到了這里，關(guān)于USACO18DEC Fine Dining G的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！