Given a dangerous vertex \(V\), if we \(U\) and \(U'\) as the closest two safe vertices (with the shortest time required to reach them), the sought value equals the sum of the times required to travel from \(U\) to \(V\), and from \(U'\) to \(V\). This is because the tour \(U\to V\to U'\) satisfies the condition, and any tour with shortest time required violates the assumption that \(U\) and \(U'\) are the two closest vertices.

Therefore, it is sufficient to find for each vertex \(V\) the closest two safe vertices and the time required to travel from each of them to \(V\) (which we will simply call “distance”). Since the edge weights are all \(1\), we can perform a BFS (Breadth-First Search): with the following two caveats:

• We have multiple starting points.
• For every vertex, we need to record not only the shortest distance from a starting point, but also the second shortest.

For the first point, we can regard that there is another vertex (sur-vertex), and there is an edge extending toward each safe vertex. For some implementations, it may be sufficient to just modify the starting point to multiple.
For the second point, it is sufficient to replace the condition in the BFS that “we never revisit a vertex that we have visited once” to “we never revisit a vertex that we have visited twice from different vertices.” Thus, instead of managing for each vertex whether we have visited, we let each vertex to take the following states: “unvisited from any starting point,” “visited only from \(u\),” and “visited from two or more starting points.” Here, note that the information we need to store in a stack is not limited to “the current vertex” and “the distance from a starting point,” but also “the starting point” (which starting point the current path has).

This way, for each vertex \(V\), we can find the two closest safe vertices and the distance from them to \(V\), allowing us to find the answer as the sum of the two distance for each dangerous vertex.
The time complexity is \(O(N+M)\), which is fast enough. Hence, the problem has been solved.

Sample code in 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;
}