POJ - 3255 Roadblocks（次短路）

     Roadblocks

       POJ - 3255 

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

                 这是一道求次短路的模板题~~大体上思路就是做两个数组d,d2,一个是表示从1到s的最短路径~一个是从n到s的最短路径~~然后最后枚举每两个有关系的段点(a,b)~那关于他们的最近的从1到n的距离就是d[a]+d2[b]+ab的长度~~吧每个距离与d[n](也就是整个图的最短路)相比较~~找出大于d[n]的最小的距离就好了；

                  但是令我疑惑的是：：假设到n有三条路，路径分别是 5 5 6，那么次短路是6而不是5（验证过）~~感觉很别扭；

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int m, n;
int head[100000];
#define inf 0x3f3f3f3f
struct edge
{
	int to;
	int ne;
	int len;
}ed[500000];
bool vis[100000];
int d[100000];
int d2[100000];
int cnt = 0;
void init()
{
	for (int s = 0; s <= 9999; s++)
	{
		head[s] = -1;

	}
	for (int s = 0; s < 490000; s++)
	{
		ed[s].ne = -1;
	}
	for (int s = 0; s <= n; s++)
	{
		d[s] = inf;
		d2[s] = inf;
	}
	memset(vis, 0, sizeof(vis));
}
void add(int from, int to, int len)
{
	ed[cnt].to = to;
	ed[cnt].len = len;
	ed[cnt].ne = head[from];
	head[from] = cnt++;
}
void spfa(int e,int d[])
{
	d[e] = 0;
	queue<int>q;
	q.push(e);
	vis[e] = 1;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int s = head[t]; ~s; s = ed[s].ne)
		{
			if (d[ed[s].to] > d[t] + ed[s].len)
			{
				d[ed[s].to] = d[t] + ed[s].len;
				if (!vis[ed[s].to])
				{
					vis[ed[s].to] = 1;
					q.push(ed[s].to);
				}
			}
		}
		vis[t] = 0;
	}
}
int main()
{
	while (cin >> n >> m)
	{
		cnt = 0;
		init();
		for (int s = 0; s < m; s++)
		{
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, c);
			add(b, a, c);
		}
		spfa(1,d);
		spfa(n, d2);
		int ans = inf;
		for (int s = 1; s <= n; s++)
		{
			for (int t = head[s]; ~t; t = ed[t].ne)
			{
				int a = ed[t].to;
				int le = ed[t].len;
				int te = d[s] + d2[a] + le;
				if (te > d[n] && ans > te)
				{
					ans = te;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}