POJ 3255 Roadblocks (次短路问题)
思想:和求最短路上的点套路一样,spfa先正着求一次,再反着求一次最短路,然后枚举每条边<i,j>找dist_zheng[i] + len<i,j> + dist_fan[j]的第二小值即可!注意不能用邻接矩阵,那样会MLE,应该用邻接表
/* poj 3255 3808K 266MS */ #include<cstdio> #include<cstring> #include<queue> #include<iostream> #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<int>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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。