从Leetcode 每日一题练习继续讨论：
3243. 新增道路查询后的最短距离 I
3243. Shortest Distance After Road Addition Queries I
题解
本题每次在增加了一条新路线后可以使用dijistra算法从0节点开始寻找到其他节点的最短路径，一旦找到到n-1节点的最短路径就停止dijistra算法。
最初会想到在添加新路径后可以直接从最初的距离减去添加的新路径中间节省的距离，但这种做法的问题在于新添加的路径可能会与之前添加过的路径有交叉，则无法确定应该减去的节省的距离是多少（如a->b为4,b->c为3，但a->d为5,d->c为1，实际选择d这条路径总距离更短）。而用dijistra算法求出的到每个节点的距离已经是最短距离，一旦确定了到n-1的距离就得到了最终结果。
代码
class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<vector<pair<int, int>>> adj(n);
for(int i = 0; i < n-1; i++) {
adj[i].push_back({i+1, 1});
}
vector<int> answer;
for(const auto& query : queries) {
int u = query[0];
int v = query[1];
adj[u].push_back({v, 1});
answer.push_back(dijkstra(adj, n, 0, n-1));
}
return answer;
}
private:
int dijkstra(const vector<vector<pair<int, int>>>& adj, int n, int start, int end) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
while(!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if(u == end) return d;
if(d > dist[u]) continue;
for(const auto& [v, weight] : adj[u]) {
if(dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist[end];
}
};