SDOI2009Elaxia的路线最短路

2019-11-11 07:38:07

字体：大中小

来源：转载

供稿：网友

题目描述

最近，Elaxia和w的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路口，M条路，经过每条路都需要一定的时间。具体地说，就是要求无向图中，两对点间最短路的最长公共路径。输入输出格式输入格式：

第一行：两个整数N和M（含义如题目描述）。第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 x1,y1和x2,y2）。接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之间有一条路，经过这条路所需要的时间为l。

输出格式：

一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）

分析： 1.本题的难点在于有多条最短路，要求最长的公共最短路。 2.首先解决一条边是否存在在最短路上的问题。 3.注意到当d[s][u]+w[u][v]+d[v][t]=d[s][t]时，边(u,v)就会在s到t的最短路径上，因此，我们不妨对4个点都进行一次最短路。 4.接下来解决最长公共最短路的问题。因为上一步我们已经选出了公共的最短路边，实际上我们就可以把问题进行分解，找到选出的边中路径最长的一条，拓扑排序+BFS就可以解决了 5.错误提醒，注意边数的大小（maxn*maxn*2）

#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>using namespace std;const int maxn=1510;const int INF=1e9;int to[maxn*maxn*2],Next[maxn*maxn*2],Begin[maxn],w[maxn*maxn*2],e;int n,m;void add(int x,int y,int z){ to[++e]=y; Next[e]=Begin[x]; Begin[x]=e; w[e]=z;}struct node{ int id,dis; bool Operator <(const node& A)const{ return A.dis<dis; }};PRiority_queue<node>q;struct Dijkstra{ int num,d[maxn],done[maxn]; void dijkstra(){ q.push((node){num,0}); for(int i=1;i<=n;i++) d[i]=INF,done[i]=0; d[num]=0; while(!q.empty()){ node f=q.top();q.pop(); int u=f.id; if(done[u]) continue; done[u]=true; for(int i=Begin[u];i;i=Next[i]){ int v=to[i]; if(d[v]>d[u]+w[i]){ d[v]=d[u]+w[i]; q.push((node){v,d[v]}); } } } }}p[10];int deg[maxn],is_edge[maxn*maxn*2];void get(int u){ for(int i=Begin[u];i;i=Next[i]){ int v=to[i]; if(p[1].d[u]+w[i]+p[2].d[v]==p[1].d[p[2].num] && (p[3].d[u]+w[i]+p[4].d[v]==p[3].d[p[4].num] || p[3].d[v]+w[i]+p[4].d[u]==p[3].d[p[4].num])){ deg[v]++;is_edge[i]=1; } }}queue<int>Q;int val[maxn*2];int solve(){ int ans=0; for(int i=1;i<=n;i++) if(!deg[i]) Q.push(i); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=Begin[u];i;i=Next[i])if(is_edge[i]){ int v=to[i]; if(val[v]<val[u]+w[i]){ val[v]=val[u]+w[i]; if(ans<val[v]) ans=val[v]; } if(!(--deg[v])) Q.push(v); } } return ans;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=4;i++) scanf("%d",&p[i].num); for(int i=1;i<=m;i++){ int u,v,l; scanf("%d%d%d",&u,&v,&l); add(u,v,l);add(v,u,l); } for(int i=1;i<=4;i++) p[i].dijkstra(); for(int i=1;i<=n;i++) get(i); printf("%d ",solve()); return 0;}

^_^

上一篇：qt 中英文翻译

下一篇：Latex-下划线