L2-001 紧急救援（最短路）

题目链接

https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

视频讲解

https://www.bilibili.com/video/BV1Br4y1W7Ay

思路

我们只需要在跑迪杰斯特拉最短路的时候注意一下松弛操作即可，我们定义 d i s [ i ] dis[i] dis[i] 表示从起点 s s s 到 i i i 点的最短路径， s u m [ i ] sum[i] sum[i] 表示从 s s s 点到 i i i 点的最多的救援队数量， c n t [ i ] cnt[i] cnt[i] 表示从 s s s 点到 i i i 点的最短路的条数， p r e [ i ] pre[i] pre[i] 表示在最优路径下 i i i 点的上一个点的位置

• 如果dis[v] > dis[u] + w，那么我们就要更新 d i s [ v ] = d i s [ u ] + w dis[v] = dis[u] + w dis[v]=dis[u]+w ， s u m [ v ] = s u m [ u ] + a [ v ] sum[v] = sum[u] + a[v] sum[v]=sum[u]+a[v]， c n t [ v ] = c n t [ u ] cnt[v] = cnt[u] cnt[v]=cnt[u] ， p r e [ v ] = u pre[v] = u pre[v]=u，并且将v点放入队列
• 如果dis[v] == dis[u] + w，那么我们就要更新 c n t [ v ] + = c n t [ u ] cnt[v] += cnt[u] cnt[v]+=cnt[u] ,因为我们可以从另外一个地方走到 v v v ，如果 s u m [ u ] + a [ v ] > s u m [ v ] sum[u] + a[v] > sum[v] sum[u]+a[v]>sum[v] 那么我们就要更新 s u m [ v ] = s u m [ u ] + a [ v ] sum[v] = sum[u] + a[v] sum[v]=sum[u]+a[v] 且更新 v v v 点的上一个节点为 p r e [ v ] = u pre[v] = u pre[v]=u （因为我们要选择最优路径）

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------

struct Node{
	int v,w;
};

int t,n,m,s,d,q,a[N];
bool vis[N];
vector E[N];
int dis[N],sum[N],cnt[N],pre[N];

void DJ(){
	priority_queue que;
	memset(dis,0x3f,sizeof dis);
	memset(pre,-1,sizeof pre);
	que.push({0,s});
	dis[s] = 0;
	cnt[s] = 1;
	sum[s] = a[s];
	while(!que.empty()){
		int u = que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = 0,l = E[u].size();i  dis[u] + w){
				dis[v] = dis[u] + w;
				sum[v] = sum[u] + a[v];
				cnt[v] = cnt[u];	
				pre[v] = u;
				que.push({dis[v],v});
			} else if(dis[v] == dis[u] + w){
				cnt[v] += cnt[u];
				if(sum[u] + a[v] > sum[v]) {
					sum[v] = sum[u] + a[v];
					pre[v] = u;
				}
			}	
		}
	}
}

void print(int p){
	stack S;
	while(p != -1) {
		S.push(p);
		p = pre[p];
	}
	while(S.size() != 1){
		coutd;
	s++,d++;
	for(int i = 1;i >a[i];
	int u,v,w;
	for(int i = 0;i >u>>v>>w;
		u++,v++;
		E[u].push_back({v,w});
		E[v].push_back({u,w});
	}
	DJ();
	cout