http://poj.org/problem?id=3255
题目大意：
有N条道路和N个路口，道路是双向的，问1号路口到N号路口的次最短路径是多少？次最短路径是比最短路径长的次短的路径。同一条边可已经过多次。
思路：
最短路和次短路不会重合，而次短路可以从最短路的某个点绕一个点得到。为啥是一个点？如果绕两个点的话会比绕一个点来的长，就不会是次短路了。
先对1和n为源点进行两次dijkstra，接下来枚举每条边，则可以算出此时的和temp=dis1[from]+disn[to]+val;或者temp=disn[from]+dis1[to]+val;如果不等于最短路则取最小值。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=5000+10;
const int MAXM=200000+10;
const int INF=0x3fffffff;
int n,r,head[MAXN],len,dis1[MAXN],disn[MAXN];
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
struct node
{
int id,val;
node(int id,int val):id(id),val(val){}
bool operator < (const node &x)const{
return val>x.val;
}
};
void dijkstra(int *dis,int s)
{
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[s]=0;
priority_queue<node> q;
q.push(node(s,0));
while(!q.empty())
{
int cur=q.top().id,val=q.top().val;
q.pop();
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] > dis[cur]+e[i].val)
{
dis[id]=dis[cur]+e[i].val;
q.push(node(id,dis[id]));
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&r))
{
memset(head,-1,sizeof(head));
len=0;
for(int i=0;i<r;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
add(to,from,val);
}
dijkstra(dis1,1);
dijkstra(disn,n);
//printf("%d %d\n",dis1[n],disn[1]);
int ans=INF;
for(int cur=1;cur<=n;cur++)
{
for(int i=head[cur];i!=-1;i=e[i].next)
{
int from=cur,to=e[i].to,val=e[i].val;
int temp=dis1[from]+disn[to]+val;
if(temp!=dis1[n] && temp <ans)
ans=temp;
temp=disn[from]+dis1[to]+val;
if(temp!=dis1[n] && temp <ans)
ans=temp;
}
}
printf("%d\n",ans);
}
return 0;
}