循环图中涉及转移的最短路径问题

Question

我正试图解决一个图形问题：
有(n+1(个城市(数量从0到n(和(m+1(条公交线路(数量从零到m(
(一条线路可能包含重复的城市，这意味着该线路有一个周期。(
每条线路覆盖多个城市，从城市i到城市j需要t_ij(不同线路的t_ij可能不同(
此外，每次上车都需要额外的transfer_time。

边缘看起来是这样的：城市i-(时间(->city2
示例1：
n=2，m=2，start=0，end=2
line0:
0--(1(->1-(1(->2.transfer_time=1
line1:
0--(2(->2.transfer_time=2
第0行取1+1+1=3，第1行取4，因此最小值为3。

示例2：
n=4，m=0，start=0，end=4
第0行：
0--(2(->1-(3(->2-(3(->3-(3(->1-(2(->4.transfer_time=1
需要1(在0上车(+2(从0到1(+1(下车上车，换乘(+2=6

我试着用Dijkstra算法来解决它，但没能处理带循环的图(比如Example2(。下面是我的代码。

struct Edge {
int len;
size_t line_no;
};
class Solution {
public:
Solution() = default;
//edges[i][j] is a vector, containing ways from city i to j in different lines
int findNearestWay(vector<vector<vector<Edge>>>& edges, vector<int>& transfer_time, size_t start, size_t end) {
size_t n = edges.size();
vector<pair<int, size_t>> distance(n, { INT_MAX / 2, -1 }); //first: len, second: line_no
distance[start].first = 0;
vector<bool> visited(n);
int cur_line = -1;
for (int i = 0; i < n; ++i) {
int next_idx = -1;
//find the nearest city
for (int j = 0; j < n; ++j) {
if (!visited[j] && (next_idx == -1 || distance[j].first < distance[next_idx].first))
next_idx = j;
}
visited[next_idx] = true;
cur_line = distance[next_idx].second;
//update distance of other cities
for (int j = 0; j < n; ++j) {
for (const Edge& e : edges[next_idx][j]) {
int new_len = distance[next_idx].first + e.len;
//transfer
if (cur_line == -1 || cur_line != e.line_no) {
new_len += transfer_time[e.line_no];
}
if (new_len < distance[j].first) {
distance[j].first = new_len;
distance[j].second = e.line_no;
}
}
}
}
return distance[end].first == INT_MAX / 2 ? -1 : distance[end].first;
}
};

有更好的练习吗？提前谢谢。

Answer 1

您的visited集合看起来有问题。"；节点"；Djikstra算法中的输入不能简单地是城市，因为这不能让你对城市内从一条线路切换到另一条线路的成本进行建模。每个节点必须是一个对，由一个城市编号和一个公交线路编号组成，表示您当前乘坐的公交线路。公交线路编号可以是-1，表示您不在公交车上，起点和终点节点的公交线路编号为-1。

然后，每条边将代表您在当前线路上乘坐前往下一个城市的费用，或在当前城市下车的费用(免费(，或在您当前城市内乘坐公交线路的费用(有换乘费用(。

你说城市的编号是从0到n，但我看到了一堆停在n - 1的循环(因为他们使用< n作为循环条件(，所以这可能是另一个问题。