# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* sho358

*iceknight1093*

**Tester & Editorialist:**# DIFFICULTY:

2268

# PREREQUISITES:

Multisource dijkstra

# PROBLEM:

You’re given an undirected graph on N vertices with M edges.

K mail carriers are present on it: the i-th of them starts at vertex X_i and has a range of D_i; meaning he can deliver mail to any vertex that’s at most distance D_i away from X_i.

Can every vertex receive its mail?

# EXPLANATION:

If K = 1, we could run a BFS from the starting point and till distance D_i; and check if all vertices are covered in \mathcal{O}(N + M).

This of course generalizes to a (slow) solution for K \gt 1: run a separate BFS for each mailman and check if all vertices are visited in the end.

Of course, the complexity here is \mathcal{O}(K\cdot (N+M)), which is too slow.

A natural optimization to try now would be to attempt a multisource BFS, however it doesn’t quite work directly because of the D_i values; so a previously visited vertex can’t simply be skipped.

## Example

Suppose we have mail carriers at 1 and 5, with D_1 = 5 and D_5 = 4.

If we BFS from 1 first, we’ll end up marking vertices 4 and 6, but not 7.

BFS-ing from 5 will then stop before marking 7, since vertices on its path are already marked.

This case also shows that trying to BFS from vertices with larger D_i first isn’t necessarily correct either.

What really matters is how many moves we have left from each vertex.

In particular, we need to know the *maximum* number of remaining steps from each vertex.

To do this, we can instead transform our algorithm to a multisource *dijkstra*!

Let \text{rem}[u] be the maximum number of remaining steps from vertex u.

First, for each mail carrier i, set \text{rem}[K_i] \gets \max(\text{rem}[K_i], D_i).

Then, for a vertex u and an adjacent vertex v, \text{rem}[v] can be updated with \text{rem}[u]-1.

Notice that this is similar to the usual dijkstra with distances, where we update \text{dist}[v] with \text{dist}[u]+wt.

So, simply running dijkstra’s algorithm on this will give us the correct values of \text{rem}[u] for all u.

Note that here, we want to keep the *maximum* value and not the minimum; make sure to implement that correctly.

Finally, if \text{rem}[u] \leq 0 for any vertex the answer is `No`

; otherwise the answer is `Yes`

.

# TIME COMPLEXITY

\mathcal{O}((N+M)\log N) for each testcase.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll t,n,m,k,x[200005],d[200005],viz[200005];
vector<ll>g[100005];
void testcase(){
cin>>n>>m>>k;
for(ll i=1;i<=n;i++)
{
viz[i]=0;
}
for(ll i=1;i<=k;i++)
{
cin>>x[i];
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
for(ll i=1;i<=k;i++)
{
cin>>d[i];
viz[x[i]]=min(-d[i],viz[x[i]]);
q.push(mp(-d[i],x[i]));
}
for(ll i=1;i<=m;i++)
{
ll x,y;
cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
while(!q.empty()){
ll x,y;
x=q.top().s;
y=q.top().f;
q.pop();
if(viz[x]!=y){
continue;
}
for(auto it : g[x]){
if(viz[x]+1<viz[it]){
viz[it]=viz[x]+1;
q.push(mp(viz[it],it));
}
}
}
int ans=1;
for(ll i=1;i<=n;i++)
{
if(viz[i]==0){
ans=0;
}
}
if(ans){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
for(ll i=1;i<=n;i++)
{
viz[i]=0;
g[i].clear();
}
}
int32_t main(){
CODE_START;
cin>>t;
while(t--){
testcase();
}
}
```

## Editorialist's code (Python)

```
from heapq import heappop, heappush
for _ in range(int(input())):
n, m, k = map(int, input().split())
pos = list(map(int, input().split()))
dis = list(map(int, input().split()))
adj = [ [] for _ in range(n)]
for i in range(m):
u, v = map(int, input().split())
adj[u-1].append(v-1)
adj[v-1].append(u-1)
dist = [-1] * n
queue = []
for i in range(k):
x, d = pos[i] - 1, dis[i] - 1
dist[x] = max(dist[x], d)
heappush(queue, (-d, x))
while queue:
rem, v = heappop(queue)
rem *= -1
if rem != dist[v] or rem == 0: continue
for x in adj[v]:
if dist[x] < rem - 1:
dist[x] = rem - 1
heappush(queue, (1 - rem, x))
print('Yes' if min(dist) >= 0 else 'No')
```