void dfs(vector<int>& signal,vector<bool> & mask, vector<vector<int> > &path, vector<vector<int> >& matrix, int nowNode, int T,int nowTime, int & minValue){ if(nowTime >= minValue) return; if(nowNode == T){ minValue = min(minValue, nowTime); return; } int waitTime = 0; if(nowTime / signal[nowNode] % 2 == 1) { waitTime = signal[nowNode] - nowTime % signal[nowNode]; } nowTime += waitTime; mask[nowNode] = true; for(int i=0;i<path[nowNode].size();i++){ if(!mask[path[nowNode][i]]){ nowTime += matrix[nowNode][path[nowNode][i]]; dfs(signal,mask,path,matrix,path[nowNode][i],T,nowTime,minValue); nowTime -= matrix[nowNode][path[nowNode][i]]; } } mask[nowNode] = false; } int minTravelTime(int N, vector < vector < int > > intersections, int M, vector < vector < int > > roads, int s, int t) { vector<bool> mask(N,false); vector<int> signal(N,0); for(int i=0;i<N;i++){ signal[intersections[i][0]] = intersections[i][1]; } vector<vector<int> > path(N); vector<vector<int> > matrix(N,vector<int>(N,0)); for(int i=0;i<M;i++){ path[roads[i][0]].push_back(roads[i][1]); path[roads[i][1]].push_back(roads[i][0]); matrix[roads[i][0]][roads[i][1]] = roads[i][2]; matrix[roads[i][1]][roads[i][0]] = roads[i][2]; } int result = 0x7fffffff; dfs(signal,mask,path,matrix,s,t,0,result); return result; }