poj3255 Roadblocks--次短路spfa

原题链接：​​http://poj.org/problem?id=3255​​

题意：n个点，标号为1到n，m条路，u，v，len，表示u与v之间路长为len，求1到n第二短路长，题目保证存在第二短路径。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

struct Edge
{
  int v;
  int len;
  int next;
};

int n, m;
int cnt;
Edge edge[200010];
int head[5010];
bool vis[5010];
int dis[5010];
int rdis[5010];

void add(int u, int v, int len)
{
  edge[cnt].v = v; edge[cnt].len = len; edge[cnt].next = head[u]; head[u] = cnt++;
  edge[cnt].v = u; edge[cnt].len = len; edge[cnt].next = head[v]; head[v] = cnt++;
}

void spfa(int s, int d[])
{
  memset(vis, 0, sizeof(vis));
  queue<int> Q;
  d[s] = 0;
  vis[s] = 1;
  Q.push(s);
  while (!Q.empty())
  {
    int u = Q.front();
    vis[u] = 0;
    Q.pop();
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
      int v = edge[i].v;
      if (d[v] > d[u] + edge[i].len)
      {
        d[v] = d[u] + edge[i].len;
        if (!vis[v])
        {
          vis[v] = 1;
          Q.push(v);
        }
      }
    }
  }
}

int main()
{
  int u, v, len;

  while (~scanf("%d%d", &n, &m))
  {
    //init
    memset(head, -1, sizeof(head));
    cnt = 0;
    fill(dis, dis + n + 1, INF);
    fill(rdis, rdis + n + 1, INF);


    while (m--)
    {
      scanf("%d%d%d", &u, &v, &len);
      add(u, v, len);
    }

    spfa(1, dis);
    spfa(n, rdis);

    int ans = INF;
    for (int i = 1; i <= n; i++)
    {
      for (int j = head[i]; j != -1; j = edge[j].next)
      {
        int v = edge[j].v;
        int len = edge[j].len;
        int d = dis[i] + rdis[v] + len;
        if (d > dis[n] && d < ans)
          ans = d;
      }
    }

    printf("%d\n", ans);
  }
  return 0;
}