危険な頂点 \(V\) に対して、安全な頂点のうちその頂点から近い（必要な移動時間が短い）方から順に \(2\) つを \(U,U'\) とすると、求めたい値は \(U\) から \(V\) への移動時間と \(U'\) から \(V\) への移動時間の総和と等しくなります。これは、\(U\to V\to U'\) という移動が条件をみたしているため求める値はそれ以下であり、それ未満の移動方法が存在する時、\(U,U'\) が近い方から \(2\) つという条件に反することから従います。

よって、すべての頂点 \(V\) について、安全な頂点のうち近い方から \(2\) つと、それらの頂点から \(V\) へ の必要な移動時間（以下、距離とします）がわかれば良いです。 すべての辺の重み（移動時間）は \(1\) であるため、幅優先探索 (BFS) で求めることができますが、通常の探索と比較して次の \(2\) 点に注意する必要があります。

• 始点の候補が複数存在する。
• 各頂点について、始点からの最短距離だけではなく、\(2\) 番目に近い頂点からの距離も記録する必要がある。

\(1\) つめについては、例えば、もう \(1\) つ別の頂点が存在し（超頂点）が存在し、そこからすべての安全な頂点へ重み \(0\) の辺が伸びていると考えることができます。実装方針によっては、単に BFS で最初に調べる頂点を複数に変更するだけで良いこともあります。
\(2\) つめについては、BFS における、「一度到達（探索）した頂点は再び調べない。」という条件を「\(2\) つの異なる頂点から到達（探索）した頂点はそれ以降調べない。」という条件に書き換えれば良いです。よって、各頂点ごとに訪ねたことがあるか無いかを管理（更新）する代わりに、「どの始点からも訪ねられたことがない」、「頂点 \(u\) からのみ訪ねられた」、「\(2\) つ以上の始点から訪ねられたことがある」のいずれの状態であるかを管理するようにすれば良いです。 また、このとき、BFS において（キューなどで）管理する情報として、「到達した頂点」と「始点からその頂点までの距離」に加えて、「始点」（どの安全な頂点を始点とした経路か）の情報も必要になることに注意してください。

このようにして、すべての頂点 \(V\) について、安全な頂点のうち近い方から \(2\) つと、それらの頂点から \(V\) へ の距離が求まれば、特に危険な頂点について \(2\) つの距離の総和として答えを求めることができます。
必要な時間計算量は \(O(N+M)\) であり、十分高速です。よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)

struct path_info{
	int from,to;
	int dist;
};

int main() {
	int n,m,u,v;
	string s;
	
	cin>>n>>m;

	vector<vector<int> >e(n);
	vector<vector<int> >f(n,vector<int>(2,-1));
	vector<vector<int> >d(n,vector<int>(2,-1));
	queue<path_info>q;

	rep(i,m){
		cin>>u>>v;
		e[u-1].push_back(v-1);
		e[v-1].push_back(u-1);
	}
	cin>>s;
	rep(i,n){
		if(s[i]=='S'){
			f[i][0]=i;
			d[i][0]=0;
			q.push({i,i,0});
		}
	}

	while(!q.empty()){
		path_info tmp=q.front();
		q.pop();
		int u=tmp.from;
		int v=tmp.to;
		int sz=e[v].size();
		rep(i,sz){
			if(f[e[v][i]][0]==-1){
				f[e[v][i]][0]=u;
				d[e[v][i]][0]=tmp.dist+1;
				q.push({u,e[v][i],tmp.dist+1});
			}
			else if((f[e[v][i]][1]==-1)&&(f[e[v][i]][0]!=u)){
				f[e[v][i]][1]=u;
				d[e[v][i]][1]=tmp.dist+1;
				q.push({u,e[v][i],tmp.dist+1});
			}
		}
	}

	rep(i,n){
		if(s[i]=='D')cout<<(d[i][0]+d[i][1])<<endl;
	}

	return 0;
}