想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处:http://blog.csdn.net/wangjian8006
题目大意:在一个图上有许多个农场,有个人从1农场出发,到他的朋友n农场去,他不想走一条最短路径,这次他想换条路走,要你帮他找一条次短路径,次短路的定义是,比最短路径长度短(可能有多条),但是不会比其他的路径长度长。而且告诉你数据中一定存在至少一条次短路。
解题思路:大致的分析下,如果我们用常规思想做这题:
删除某一条边求最短路径,找出的最短路径比最短路径短,但是比其他路径长就是的了
这样做的时间复杂度是,spfa的时间复杂度大约是O(KE),E为边的总数=200000
然后枚举边O(E),那么总的时间复杂度为O(KE^2),大约是K*400亿。这样明显会超时。
最短路明显不会是次短路,因为题目说了次短一定是存在的,那么他们不可能重合,这样次短路肯定是最短路中某一条边不走,而走了其他边再回到最短路上,而且不可能绕两个地方,只可能绕一个地方,因为明显绕两个地方比绕一个地方的路径长,明显不是次短路了
所以我们枚举每条边<s,t>
有d[s]---》源点到s的最短距离
有dr[t]----》t到汇点的最短距离,这样就需要从t到s求一次最短路得到了
len<s,t>表示<s,t>这条边的长度
然后我们枚举每一条边有:tmp=d[s]+dr[t]+len<s,t>
找出其中比最短路小但是比其他路长的一个值就是次短路径了
/* Memory 2644K Time 157MS */ #include <iostream> #include <queue> using namespace std; #define MAXV 5010 #define MAXE 200100 #define INF 1<<29 typedef struct{ int t,w,next; }Edge; Edge edge[MAXE]; int d[MAXV],dr[MAXV]; int n,m,edge_sum; int head[MAXV]; bool vis[MAXV]; void init(){ memset(head,-1,sizeof(head)); edge_sum=0; for(int i=1;i<=n;i++) d[i]=dr[i]=INF; } void addedge(int s,int t,int w){ edge[edge_sum].t=t; edge[edge_sum].w=w; edge[edge_sum].next=head[s]; head[s]=edge_sum++; } void spfa(int source,int dt[]){ int i,v,u; queue <int>q; memset(vis,0,sizeof(vis)); dt[source]=0; vis[source]=1; q.push(source); while(!q.empty()){ v=q.front();q.pop(); vis[v]=0; for(i=head[v];i!=-1;i=edge[i].next){ u=edge[i].t; if(dt[v]+edge[i].w<dt[u]){ dt[u]=dt[v]+edge[i].w; if(!vis[u]){ vis[u]=1; q.push(u); } } } } } int main(){ int a,b,c; int ans,tmp,i; while(~scanf("%d%d",&n,&m)){ init(); while(m--){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); addedge(b,a,c); } spfa(1,d); spfa(n,dr); ans=INF; for(i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=edge[j].next){ b=edge[j].t; c=edge[j].w; tmp=d[i]+dr[b]+c; if(tmp>d[n] && ans>tmp){ ans=tmp; } } } printf("%d\n",ans); } return 0; }