解法有很多奇葩的地方，比如可以到达终点再跳回去再跳回来（比如有两个点）。。。。反正就是不能有最短路，不过没关系，算法都能给出正确结果
思想：和求最短路上的点套路一样，spfa先正着求一次，再反着求一次最短路，然后枚举每条边
找dist_zheng[i] + len
+ dist_fan[j]的第二小值即可！注意不能用邻接矩阵，那样会MLE，应该用邻接表
/*
poj 3255
3808K 266MS
*/
#include
#include
#include
#include
#define MAXN 200005 #define MAX_INT 2147483647 using namespace std; int last[5005], dist_1[5005], dist_2[5005], n, m, gra[5005][5005]; bool mark[MAXN]; struct node { int u; int v; int w; int next; node() { u = v = w = next = 0; } }edge[MAXN]; void spfa( int dist[5005], int s ) { queue
myQueue; dist[s] = 0; memset(mark, false, sizeof(mark)); mark[s] = true; myQueue.push(s); while( !myQueue.empty() ) { int x = myQueue.front(); myQueue.pop(); mark[x] = false; int t = last[x]; while( t ) { if( dist[ edge[t].v ] > dist[x] + edge[t].w ) { dist[ edge[t].v ] = dist[x] + edge[t].w; if( !mark[ edge[t].v ] ) myQueue.push( edge[t].v ); } t = edge[t].next; } } } int main() { cin >> n >> m; for(int i = 1;i <= m;i ++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); edge[i].u = edge[i + m].v = a; edge[i].v = edge[i + m].u = b; edge[i].w = edge[i + m].w = c; edge[i].next = last[a]; last[a] = i; edge[i + m].next = last[b]; last[b] = i + m; } memset( dist_1, 1, sizeof(dist_1) ); spfa( dist_1, 1 ); memset( dist_2, 1, sizeof(dist_2) ); spfa( dist_2, n ); int ans = MAX_INT, tmp = MAX_INT; for(int i = 1;i <= n;i ++) { int t = last[i]; while( t ) { if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < tmp ) { ans = tmp; tmp = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w; } else if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < ans && dist_1[i] + dist_2[ edge[t].v ] + edge[t].w != tmp ) ans = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w; t = edge[t].next; } } cout << ans << endl; return 0; }