Я работал над этой проблемой и решил использовать алгоритм Дейкстры для ее решения. Однако я не уверен, как учитывать заблокированный путь от a до b и как учитывать время ожидания 60 минут, когда путь заблокирован. Нужно ли более одного SSSP для решения этой проблемы? Как мне подойти к решению этой проблемы?
Изображение предоставлено: Национальный университет Сингапура
Мой код выглядит следующим образом:
struct road_tuples{
int u;
int v;
int w;
};
int minDistance(int dist[], bool sptSet[], int V){
int min = INT_MAX;
int min_index;
for(int v = 0; v<V;v++){
if(sptSet[v]==false && dist[v]<=min){
min = dist[v];
min_index = v;
}
}
return min_index;
}
//dijkstra using adj matrix
int minMinutes(int V, int a, int b, int c, int d, int E, road_tuples list){
//create adjacency matrix
int graph[V][V];
//fill in adjacency matrix
for(int i=0;i<E;i++)
graph[list.u][list.v] = list.w;
graph[list.v][list.u] = list.w;
//no path from a to b
graph[a][b] = 0;
graph[b][a] = 0;
//assign source
int src = c;
//will hold shortest distance from src to i
int dist[V];
//sptSet[i] will be true if i included in SSSP
bool sptSet[V];
//init all distances to infinite, set sptSet[i] as false
for(int i =0; i < V; i++){
dist[i] = INT_MAX;
sptSet[i] = false;
}
//set dist from source to itself as 0
dist[src] = 0;
//find shortest path for all vertices
for(int count =0; count< V-1; count++){
int u = minDistance(dist, sptSet, V);
sptSet[u] = true;
for(int v=0; v<V; v++){
if(!sptSet[v] && graph[u][v] && dist[u]!= INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
return dist[d];
}