POJ 3255 Roadblocks --次短路径
由于次短路一定存在,则可知次短路一定是最短路中某一条边不走,然后回到最短路,而且只是一条边,两条边以上不走的话,就一定不会是次短路了(即以边换边才能使最小)。所以可以枚举每一条边,算出从起点到这条边起点的最短距离,以及从终点到这条边终点的最短距离,再加上这条边的权值,看是否是次短路(比最短路总权值大的最小权值的路径)
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #define Mod 1000000007 using namespace std; #define N 5007 vector<pair<int,int> > G[200005]; int ds[N],dt[N],vis[N]; int n,m,k; void SPFA(int s,int *d) { int i,u,v; queue<int> que; memset(vis,0,sizeof(vis)); d[s] = 0; vis[s] = 1; que.push(s); while(!que.empty()) { v = que.front(); que.pop(); vis[v] = 0; //边允许重复走 for(i=0;i<G[v].size();i++) { u = G[v][i].first; if(d[v] + G[v][i].second < d[u]) { d[u] = d[v] + G[v][i].second; if(!vis[u]) { vis[u] = 1; que.push(u); } } } } } int main() { int u,v,w; int res,tmp,i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) G[i].clear(); for(i=1;i<=n;i++) ds[i] = dt[i] = Mod; while(m--) { scanf("%d%d%d",&u,&v,&w); G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } SPFA(1,ds); SPFA(n,dt); res = Mod; for(i=1;i<=n;i++) for(j=0;j<G[i].size();j++) { u = i; v = G[i][j].first; w = G[i][j].second; tmp = ds[u] + dt[v] + w; if(tmp > ds[n] && res > tmp) res = tmp; } printf("%d\n",res); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。