学步园

题意 ： 求一张图里面的次短路，可以重复走一个节点，并且长度绝对大于最短路。

思路 ： 用Dijkstra算法求出每个点到起始点和终止点的最短距离， 然后枚举每一条边(ds[a[i]] + de[b[i]] + w[i])和(ds[a[i]] + de[b[i]] + w[i] * 3)，选择一条大于最短路的次短路。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF = 283829894;
const int maxn = 100005;

struct Edge{
      int to, next, c;
}edge[maxn<<1];

struct Dist{
      int d, num;
      Dist(){}
      Dist(int a, int b) : d(a), num(b) {}
      bool operator < (const Dist &cmp)const {
            return d > cmp.d;
      }
};

int head[maxn], ds[maxn], de[maxn], E;
int n, m, a[maxn<<1], b[maxn<<1], w[maxn<<1], vis[maxn];

void Dijkstra(int d[], int sx){
      fill(d+1, d+n+1, INF); d[sx] = 0;
      memset(vis, 0, sizeof(vis));
      priority_queue<Dist> q;
      q.push(Dist(d[sx], sx));
      while (!q.empty()){
            Dist tmp = q.top(); q.pop();
            int x = tmp.num;
            if (vis[x])continue;
            vis[x] = 1;
            for (int i = head[x]; i != -1; i = edge[i].next){
                  int to = edge[i].to, c = edge[i].c;
                  if (d[to] > d[x] + c){
                        d[to] = d[x] + c;
                        q.push(Dist(d[to], to));
                  }
            }
      }
      return ;
}

void init(){
      E = 0;
      memset(head, -1, sizeof(head));
}

void add_edge(int u, int to, int c){
      edge[E].to = to;
      edge[E].c = c;
      edge[E].next = head[u];
      head[u] = E++;
}

int main(){
      int T;
      scanf("%d", &T);
      for (int cas = 1; cas <= T; cas++){
            init();
            scanf("%d%d", &n, &m);
            for (int i = 1; i <= 2*m; i+=2){
                  scanf("%d%d%d", &a[i], &b[i], &w[i]);
                  a[i+1] = b[i]; b[i+1] = a[i]; w[i+1] = w[i];
                  add_edge(a[i], b[i], w[i]);
                  add_edge(a[i+1], b[i+1], w[i+1]);
            }
            Dijkstra(ds, 1); Dijkstra(de, n);
            int Min = ds[n], ret = INF;
            for (int i = 1; i <= 2*m; i++){
                  int tmp1 = ds[a[i]] + de[b[i]] + w[i];
                  int tmp2 = tmp1 + 2 * w[i];
                  if (tmp1 > Min){ret = min(ret, tmp1);}
                  else if (tmp2 > Min){ret = min(ret, tmp2);}
                  else ;
            }
            printf("Case %d: %d\n", cas, ret);
      }
      return 0;
}

PS  : 一开始的想法是使用Dijkstra算法推出所有点到起始点和终止点的最短距离，然后在去枚举   点  ， 但是因为有可能次短路是最短路上的最短边重复走3次形成的， 所以要去记录最短路上的最短边感觉代码不容易实现，后来网上看了下是枚举边后就豁然开朗了。 : )

另外，如果求K短路呢？有没有什么好的算法呢？值得思考 ... (K - Shortest Path click here)