学到现在就做过两道次短路的题。
A*这辈子都不可能学的。两个不同的方法分别是dist2法和删边法。
dist2法
做法就是类似于dist数组那样，再弄一个dist2数组，代表次短路径。
更新的话就要比较多的判断关系，关键的最短路算法判断是这样的：
void dijkstra(int s, int t){ memset(dist, 0x3f, sizeof dist); memset(dist2, 0x3f, sizeof dist2);// 0x7f??? std::priority_queue heap; dist[s] = 0; heap.push((Heapnodes){dist[s], s}); while(!heap.empty()) { Heapnodes x = heap.top(); heap.pop(); int d = x.d, u = x.u; if(d != dist[u]) continue; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if(dist[u] + e[i].weight < dist[v]) { dist2[v] = dist[v]; dist[v] = dist[u] + e[i].weight; heap.push((Heapnodes){dist[v], v}); } if(dist[u] + e[i].weight > dist[v] && dist[u] + e[i].weight < dist2[v]) { dist2[v] = dist[u] + e[i].weight; heap.push((Heapnodes){dist[v], v}); } if(dist2[u] + e[i].weight < dist2[v]) { dist2[v] = dist2[u] + e[i].weight; //heap.push((Heapnodes){dist[v], v}); } } }} 其实也不知道对不对，因为Rodeblock那道题数据太水了。我觉得大概率是不对的。
删边法
求次短路我更倾向于第二种方法。
思路也比较清晰：先求最短路，然后再枚举最短路上的每一条路径，删去后再跑最短路，这些最短路的最大值就是次短路。
做法除了要写两个最短路以外没有什么大问题。要枚举路径就多一个pre数组而已，删边就记录一下下标，然后枚举边的时候判断是否合法即可。
这是P1491的代码：
#include#include #include #include #include const int maxn = 205;const double INF = 1e15;struct Edges{ int next, to; double weight;} e[100005];int head[maxn], tot;double x[maxn], y[maxn];int n, m;bool vis[maxn];double dist[maxn];int pre[maxn];double dis(int u, int v){ return sqrt((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]));}void link(int u, int v, double w){ e[++tot] = (Edges){head[u], v, w}; head[u] = tot;}void spfa(){ std::queue q; for(int i = 1; i <= n; i++) dist[i] = INF; dist[1] = 0; q.push(1); vis[1] = true; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if(dist[u] + e[i].weight < dist[v]) { dist[v] = dist[u] + e[i].weight; // tag pre[v] = u; if(!vis[v]) { q.push(v); vis[v] = true; } } } }}void spfa2(int nou, int nov){ memset(vis, false, sizeof vis); for(int i = 1; i <= n; i++) dist[i] = INF; std::queue q; dist[1] = 0; q.push(1); vis[1] = true; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if((u == nou && v == nov) || (u == nov && v == nou)) continue; if(dist[u] + e[i].weight < dist[v]) { dist[v] = dist[u] + e[i].weight; if(!vis[v]) { q.push(v); vis[v] = true; } } } }}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lf%lf", &x[i], &y[i]); } while(m--) { int u, v; scanf("%d%d", &u, &v); link(u, v, dis(u, v)); link(v, u, dis(v, u)); } spfa(); double ans = INF, mem = dist[n]; for(int i = n; i != 1; i = pre[i]) { spfa2(i, pre[i]); ans = std::min(ans, dist[n]); } //printf("%.2lf\n", mem); if(ans == INF) printf("-1\n"); printf("%.2lf\n", ans); return 0;}