单源次短路 例题AcWing 383. 观光
算法选择: dijkstra算法(具有拓扑序)。
思路分析
思路与树形DP中的树上最长路径 相似,同时记录最短路和次短路。
如果最短路被更新,那么就用之前的最短路来更新次短路。
如果最短路不能被更新但是次短路可以被更新,那么直接更新次短路。
模板
// 0记录最短, 1记录次短
struct V{
int id,t,dist;
bool operator > (const V & x) const {
return dist > x.dist;
}
};
int dijkstra(){
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[S][0] = 0;
priority_queue<V,vector<V>,greater<V>> heap;
heap.push({S,0,0});
while(!heap.empty()){
auto u = heap.top();heap.pop();
int v = u.id, t = u.t, d = u.dist;
if(st[v][t])continue;
st[v][t] = true;
for(int i = h[v]; ~i ; i = ne[i]){
int j = e[i];
if(dist[j][0] > d + w[i]){ // 更新最短路
dist[j][1] = dist[j][0],heap.push({j,1,dist[j][1]});
dist[j][0] = d + w[i],heap.push({j,0,dist[j][0]});
}
else if(dist[j][1] > d + w[i]){ // 更新次短路
dist[j][1] = d + w[i], heap.push({j,1,dist[j][1]});
}
}
}
}