Problem D. 送快递 【最短路 | 反悔贪心（堆维护）】

Flash 是 A 城里的一位快递小哥，A 城中共有 n + 1 家住户，门牌号依次为 0, 1, 2, · · · , n，它们通过 m 条双向道路相连。Flash 位于的快递站门牌号为 0，保证可以到达 A 城中的任意一家住户。 Flash 今天（第一天）接到了一个派送任务，需要向每一家住户派送一个神秘快递，但是 Flash 的能力 有限，每天只能派送一件快递且只能从快递站出发。每一件快递都标明了一个截止日期，Flash 需要在 第 i 个快递的截止日期 ti 前将该快递送至门牌号为 i 的住户手中。例如，若在第 3 天，某个未被派送快 递的截止日期为 3，当天派送它则可以成功送达，但如果同时有两个截止日期为 3 的未被派送的快递， 那么 Flash 只能选择一个进行派送，另外一个必定超时。 对于每一件快递而言，其派送费等于最短派送路径的长度。但是，若某个快递超时，Flash 将会被处以 相应派送费金额的罚款，并且不会得到任何派送费！ 收益指总派送费减总罚款，请你帮忙计算出 Flash 此次任务的最大收益为多少？

操作对象是一个结构体，分别记录截止时间和最短距离。方法是贪心，问题是怎么贪心。

首先想正面贪心，截止时间小的在前面，选出同一时间里面最短距离最大的，但是明显有bug。

法一：反向贪心，不难发现每一天只能对应送一个快递，用vis数组记录当前天有没有快递要送。一共送n天。这样想就需要按照最短距离从大到小排序，然后从截止时间开始从后往前遍历即可。

#include
typedef long long ll;
using namespace std;
const ll N = 1e5 + 10, M = 2e5 + 10;
ll h[N], w[M], ne[M], e[M], idx;
struct Node
{
	ll d, t;
	bool operator < (const Node & x) const {
		if(d == x.d) return t > x.t;
		else return d > x.d;
	}
}ed[N];
void add(ll a, ll b, ll c)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
ll dis[N];
bool st[N], vis[N];
ll n,m;
void spfa()
{
	memset(dis, 0x3f, sizeof dis);
	queue q;
	q.push(0);
	dis[0] = 0;
	st[0] = 1;
	while(q.size())
	{
		ll t = q.front();
		q.pop();
		st[t] = 0;
		for (ll i = h[t]; ~i; i = ne[i])
		{
			ll j = e[i];
			if(dis[j] > dis[t] + w[i]) {
				dis[j] = dis[t] + w[i];
				if(!st[j]) {
					st[j] = 1;
					q.push(j);
				}
			}
		}
	}
}
 
int main(){
	std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m -- ) {
    	ll u, v, w;
    	cin >> u >> v >> w;
    	add(u, v, w), add(v, u, w);
    }    
    spfa();
    for (ll i = 1, x; i <= n; i ++ ) {
    	cin >> x;
    	ed[i] = {dis[i], x};
    }
 
    ll ans = 0;
    sort(ed + 1, ed + 1 + n);
    for (ll i = 1; i <= n; i ++ ) {
    	bool ok = false;
    	for (ll j = ed[i].t; j >= 1; j -- ) {
    		if(!vis[j])
    		{
    			vis[j] = 1;
    			ans += ed[i].d;
    			ok = true;
    			break;
    		}
    	}
    	if(!ok) ans -= ed[i].d;
    }
    cout << ans << '\n';
	return 0;
}

---

法二：反悔贪心

用堆维护，堆用优先队列写。

道理非常简单。首先小根堆顶是最小值，每次拿堆顶和当前的值比较，如果不满足条件pop，所以我们最终留在队列里的是较大值，所以用小根堆。

while (qu.size() >= d[i].t && qu.top() < d[i].dis) qu.pop(); qu.size() >= d[i].t是因为如果t=4，那么你最多选出来最大值的个数就只能是四个，因为截止日期就是4，只有所有小于等于4的能被维护，一天送一个一共送4天。比如 1 1 3 4可以 1 1 2 3 4不行，这样必定使得第五天的4超时。这其实和上面的解法一个思路。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n, m, u, v, w, vis[100005];
vector < pair < int, int> > edg[100005];
long long dis[100005], a[100005], maxd[100005], ans;
priority_queue< long long, vector <long long >, greater< long long>> qu;
struct DATE {
	long long t, dis;
	inline bool operator < (const DATE& d2) const {
		return t < d2.t;
	}
} d[100005];
void SPFA() {
	for (int i = 1; i <= n; i++) dis[i] = 1e10;
	queue < int > qu;
	qu.push(0);
	while (!qu.empty()) {
		u = qu.front(), qu.pop();
		vis[u] = 0;
		for (int i = 0; i < edg[u].size(); i++) {
			v = edg[u][i].first;
			if (dis[v] > dis[u] + edg[u][i].second) {
				dis[v] = dis[u] + edg[u][i].second;
				if (!vis[v])qu.push(v), vis[v] = 1;
			}
		}
	}
	return;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		edg[u].push_back({ v, w });
		edg[v].push_back({ u, w });
	}
	SPFA();
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i].t);
		d[i].dis = dis[i];
		ans += dis[i];
	}
	sort(d + 1, d + n + 1);
	qu.push(d[1].dis);
	for (int i = 2; i <= n; i++) {
		while (qu.size() >= d[i].t && qu.top() < d[i].dis) qu.pop();
		if (qu.size() < d[i].t) qu.push(d[i].dis);
	}
	while (!qu.empty()) ans -= qu.top() * 2, qu.pop();
	printf("%lld\n", -ans);
	return 0;
}

略：

道理非常简单。首先小根堆顶是最小值，每次拿堆顶和当前的值比较，如果不满足条件pop，所以我们最终留在队列里的是较大值，所以用小根堆。

while (qu.size() >= d[i].t && qu.top() < d[i].dis) qu.pop(); qu.size() >= d[i].t是因为如果t=4，那么你最多选出来最大值的个数就只能是四个，因为截止日期就是4，只有所有小于等于4的能被维护，一天送一个一共送4天。比如 1 1 3 4可以 1 1 2 3 4不行，这样必定使得第五天的4超时。这其实和上面的解法一个思路。

道理非常简单。首先小根堆顶是最小值，每次拿堆顶和当前的值比较，如果不满足条件pop，所以我们最终留在队列里的是较大值，所以用小根堆。

while (qu.size() >= d[i].t && qu.top() < d[i].dis) qu.pop(); qu.size() >= d[i].t是因为如果t=4，那么你最多选出来最大值的个数就只能是四个，因为截止日期就是4，只有所有小于等于4的能被维护，一天送一个一共送4天。比如 1 1 3 4可以 1 1 2 3 4不行，这样必定使得第五天的4超时。这其实和上面的解法一个思路。