学步园

http://poj.org/problem?id=3255

题意:某街区共有R条道路、N个路口。道路可以双向通行。问1号路口到N号路口的次短路长度是多少? 次短路指的是比最短路长度长的次短的路径。同一条边可以经过多次。

解法一：
     用最短路算法，在距离更新的时候，同时更新最短距离和次短距离。
解法二：
     先求出起点到所有点的最短距离d1[]和终点到所有点的最短距离d2[]， 然后枚举每条边（双向边），即假定这条边在次短路中，记录每次的结果，这样最后就能得出次短的距离。
     ans = min(ds[v] + dt[u] + value[v][u]) e(v,u)∈ E
解法三：
     用求第k短路算法做。例题：POJ 2449 Remmarguts' Date

--------------------------------------------------------------------------------------------

解法一代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 5000 + 10;
const int INF = 1000000000;
typedef pair<int, int> P;
int N, R;
struct edge {
    int to, cost;
};
vector<edge> G[maxn];
int dist[maxn];
int dist2[maxn];
void solve() {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist+N, INF);
    fill(dist2, dist2+N, INF);
    dist[0] = 0;
    que.push(P(0,0));
    while(!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second, d = p.first;
        if(dist2[v] < d) continue;
        for(int i=0; i<G[v].size(); ++i) {
            edge &e = G[v][i];
            int d2 = d + e.cost;
            if(dist[e.to]>d2) {
                swap(dist[e.to], d2);
                que.push(P(dist[e.to], e.to));
            }
            if(dist2[e.to] >d2&&dist[e.to] <d2) {
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }
    printf("%d\n",dist2[N-1]);
}

int main() {
    int i, a, b, c;
    edge e;
    while(~scanf("%d%d",&N,&R)) {
        for(i=0; i<R; ++i) {
            scanf("%d%d%d", &a, &b, &c);
            a--,b--;
            e.to = b, e.cost = c;
            G[a].push_back(e);
            e.to = a;
            G[b].push_back(e);
        }
        solve();
    }
    return 0;
}