Multi-source bfs idea is good. But to make it work for shop nodes, in addition to the distance to the nearest shop, you also need to memorize what the nearest shop is. So you would have O(n^2) states: dist[v][shop]. Are all these states actually needed? Can you reduce the number of states?

If there are already two shops that can reach a node, and now a third shop reaches that node. Is this third shop ever useful?

No! A third shop is never useful. So you only need two states for each node. dist[v][1] and dist[v][2] and you need to remember what shop they came from, so also keep track of shop[v][1] and shop[v][2].

Read all hints first. Initialize all dist[v][1] = dist[v][2] = INF for all nodes. Then set dist[v][1] = 0, shop[v][1] = v, for all shops v, and insert the pairs (v, 1) into a queue. Then do a bfs. For a pair (v, 1) update all neighbors u of v, such that

• if dist[u][1] = INF, then set dist[u][1] = dist[v][1] + 1 and shop[u][1] = shop[v][1]
• if dist[u][2] = INF and dist[u][1] != INF and shop[u][1] != shop[v][1], then set dist[u][2] = dist[v][1] + 1 and shop[u][1] = shop[v][1]

For a pair (v, 2) update all neighbors u of v, such that

• if dist[u][2] = INF, then set dist[u][2] = dist[v][2] + 1 and shop[u][2] = shop[v][2]

Now you can find the nearest shop from every node by considering dist[v][1] (only if shop[v][1] != v) and dist[v][2] (here you don't need to check, because one of the two shops is guaranteed to be different from v)