题目要求次短路径，每条路可以走多次。
本题的实现方法是分别对1和n进行两次Dijkstra，然后枚举边，产生新的一条路，即两点分别到1和n的距离和加上这条边的距离。如果这样计算后不存在次短路径，那么答案就是 （最短路径+2*最短的边长）。
#include <stdio.h>
const int R = 100000+5;
const int N = 5000+ 5;
const int MAX = 1<<30;
struct Line{
int s, t;
int len;
}line[R];
struct Link{
int t;
int len;
Link *next;
};
struct Node{
Link head;
void Insert( int t, int len ){
Link *p = new Link();
p->t = t; p->len = len;
p->next = head.next;
head.next = p;
}
}node[N];
void Dijkstra( int n, int source, int* d )
{
int flag[N] = {0} ;
int i, j;
for ( i=0; i<n; i++ )
d[i] = MAX;
d[source] = 0;
for ( i=0; i<n; i++ )
{
int min = 0;
int p = 0;
for ( j=0; j<n; j++ )
{
if ( (flag[j]==0 ) && (p==0 || d[j]<d[min]) )
{
p = 1;
min = j;
}
}
flag[min] = 1;
Link *tmp = node[min].head.next;
for ( ; tmp!=NULL; tmp=tmp->next )
{
if ( d[tmp->t]>d[min]+tmp->len )
d[tmp->t] = d[min]+tmp->len;
}
}
}
int dis0[N];
int disn[N];
int minRoad;
void Find( int n, int r )
{
int i;
int minLen = dis0[n-1];
int secLen = MAX;
for ( i=0; i<r; i++ )
{
int cur = dis0[line[i].s] + disn[line[i].t] + line[i].len;
if ( cur<secLen && cur>minLen )
secLen = cur;
cur = dis0[line[i].t] + disn[line[i].s] + line[i].len;
if ( cur<secLen && cur>minLen )
secLen = cur;
}
if ( secLen==MAX )
printf("%d/n", minLen+2*minRoad );
else
printf("%d/n", secLen );
}
int main ()
{
int n, r;
int i;
scanf("%d %d", &n, &r );
minRoad = MAX;
for ( i=0; i<r; i++ )
{
scanf("%d %d %d", &line[i].s, &line[i].t, &line[i].len );
line[i].s--;line[i].t--;
if ( line[i].len<minRoad )
minRoad = line[i].len;
node[line[i].s].Insert( line[i].t, line[i].len );
node[line[i].t].Insert( line[i].s, line[i].len );
}
Dijkstra( n, 0, dis0 );
Dijkstra( n, n-1, disn );
Find( n, r );
return 0;
}