首页 > 代码库 > P2149 [SDOI2009]Elaxia的路线
P2149 [SDOI2009]Elaxia的路线
题目描述
最近，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：
9 101 6 7 81 2 12 5 22 3 33 4 23 9 54 5 34 6 44 7 25 8 17 9 1
输出样例#1：
3
说明
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。
首先跑四遍SPFA求出各个点之间的最短路
然后暴力枚举每一个点，跑出一个新的图
再在图上跑拓扑
找出最大值
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=200001; 8 int n,m; 9 int x11,y11,x22,y22; 10 struct node 11 { 12 int u,v,w,next; 13 }edge[MAXN],newedge[MAXN]; 14 int num=1; 15 int head[MAXN]; 16 int newnum=1; 17 int newhead[MAXN]; 18 int dis[5][MAXN]; 19 int vis[MAXN]; 20 int ans=0; 21 int rudu[MAXN]; 22 void SPFA(int k,int now) 23 { 24 queue<int>q; 25 memset(vis,0,sizeof(vis)); 26 memset(dis[now],0x7f,sizeof(dis[now])); 27 q.push(k);vis[k]=1;dis[now][k]=0; 28 while(q.size()!=0) 29 { 30 int p=q.front();q.pop(); 31 for(int i=head[p];i!=-1;i=edge[i].next) 32 { 33 int where=edge[i].u; 34 int to=edge[i].v; 35 if(dis[now][to]>dis[now][p]+edge[i].w) 36 { 37 dis[now][to]=dis[now][p]+edge[i].w; 38 if(vis[to]==0) 39 {vis[to]=1;q.push(to);} 40 } 41 } 42 } 43 /*for(int i=1;i<=n;i++) 44 cout<<dis[now][i]<<" "; 45 cout<<endl;*/ 46 } 47 void topsort() 48 { 49 int dis[MAXN]; 50 memset(dis,0,sizeof(dis)); 51 queue<int>q; 52 for(int i=1;i<=n;i++) 53 if(rudu[i]==0) 54 q.push(i); 55 while(q.size()!=0) 56 { 57 int p=q.front();q.pop(); 58 ans=max(ans,dis[p]); 59 for(int i=head[p];i!=-1;i=edge[i].next) 60 { 61 dis[newedge[i].v]=max(dis[newedge[i].v],dis[p]+newedge[i].w); 62 rudu[newedge[i].v]--; 63 if(rudu[newedge[i].v]==0) 64 q.push(newedge[i].v); 65 } 66 } 67 } 68 void build() 69 { 70 for(int i=1;i<=n;i++) 71 for(int j=head[i];j!=-1;j=edge[j].next) 72 { 73 int where=edge[j].u;int to=edge[j].v; 74 if(dis[1][i]+edge[j].w+dis[2][to]==dis[1][y11]&&dis[3][i]+edge[j].w+dis[4][to]==dis[3][y22]) 75 { 76 newedge[newnum].u=edge[j].u; 77 newedge[newnum].v=edge[j].v; 78 newedge[newnum].w=edge[j].w; 79 newedge[newnum].next=newhead[edge[newnum].u]; 80 rudu[newedge[newnum].v]++; 81 newhead[edge[newnum].u]=newnum++; 82 } 83 } 84 topsort(); 85 86 for(int i=1;i<=n;i++)newhead[i]=-1; 87 88 for(int i=1;i<=n;i++) 89 { 90 for(int j=head[i];j!=-1;j=edge[j].next) 91 { 92 int where=edge[j].u;int to=edge[j].v; 93 if(dis[1][i]+edge[j].w+dis[2][to]==dis[1][y11]&&dis[3][to]+edge[j].w+dis[4][i]==dis[3][y22]) 94 { 95 newedge[newnum].u=edge[j].u; 96 newedge[newnum].v=edge[j].v; 97 newedge[newnum].w=edge[j].w; 98 newedge[newnum].next=newhead[edge[newnum].u]; 99 rudu[newedge[newnum].v]++;100 newhead[edge[newnum].u]=newnum++;101 }102 }103 }104 topsort();105 printf("%d",ans);106 }107 int main()108 {109 scanf("%d%d",&n,&m);110 for(int i=1;i<=n;i++)111 head[i]=-1,112 newhead[i]=-1;113 scanf("%d%d%d%d",&x11,&y11,&x22,&y22);114 for(int i=1;i<=m;i++)115 {116 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);117 edge[num].next=head[edge[num].u];118 head[edge[num].u]=num++;119 edge[num].u=edge[num-1].v;120 edge[num].v=edge[num-1].u;121 edge[num].w=edge[num-1].w;122 edge[num].next=head[edge[num].u];123 head[edge[num].u]=num++;124 }125 SPFA(x11,1);126 SPFA(y11,2);127 SPFA(x22,3);128 SPFA(y22,4);129 build();130 return 0;131 }
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct edge 6 { 7 int nxt,to,dis; 8 }a[3000010]; 9 int head[10000];10 int Head[10000];11 int lv[10000];12 bool b[10000];13 int s1[10000],t1[10000],s2[10000],t2[10000];14 int n,m,x1,y1,x2,y2,x,y,z,num,ans;15 queue<int>q;16 inline int max(int a,int b){return a>b?a:b;}17 18 inline void add(int head[],int x,int y,int z)19 {a[++num].nxt=head[x],a[num].to=y,a[num].dis=z,head[x]=num;}20 21 inline void Add(int head[],int x,int y,int z){add(head,x,y,z);add(head,y,x,z);}22 inline void SPFA(int S,int dis[])23 {24 memset(dis,0x3f,sizeof (int)*1510);25 dis[S]=0;q.push(S);26 while(!q.empty())27 {28 int tmp=q.front();q.pop();29 b[tmp]=0;30 for(int i=head[tmp];i;i=a[i].nxt)31 if(dis[a[i].to]>dis[tmp]+a[i].dis)32 {33 dis[a[i].to]=dis[tmp]+a[i].dis;34 if(!b[a[i].to]) b[a[i].to]=1,q.push(a[i].to);35 }36 }37 }38 inline void topologysort()39 {40 int dis[10000];41 memset(dis,0,sizeof(dis));42 for(int i=1;i<=n;i++)43 if(!lv[i]) q.push(i);44 while(!q.empty())45 {46 int tmp=q.front();q.pop();47 ans=max(ans,dis[tmp]);48 for(int i=Head[tmp];i;i=a[i].nxt)49 {50 dis[a[i].to]=max(dis[a[i].to],dis[tmp]+a[i].dis);51 if(!--lv[a[i].to]) q.push(a[i].to);52 }53 }54 }55 int main()56 {57 scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);58 for(int i=1;i<=m;i++)59 scanf("%d%d%d",&x,&y,&z),Add(head,x,y,z);60 SPFA(x1,s1);SPFA(y1,t1);61 SPFA(x2,s2);SPFA(y2,t2);62 63 for(int tmp=1;tmp<=n;tmp++)64 for(int i=head[tmp];i;i=a[i].nxt)65 if(s1[tmp]+a[i].dis+t1[a[i].to]==s1[y1]&&s2[tmp]+a[i].dis+t2[a[i].to]==s2[y2])66 add(Head,tmp,a[i].to,a[i].dis),lv[a[i].to]++;67 topologysort();68 69 memset(Head,0,sizeof(Head));70 for(int tmp=1;tmp<=n;tmp++)71 for(int i=head[tmp];i;i=a[i].nxt)72 if(s1[tmp]+a[i].dis+t1[a[i].to]==s1[y1]&&s2[a[i].to]+a[i].dis+t2[tmp]==s2[y2])73 add(Head,tmp,a[i].to,a[i].dis),lv[a[i].to]++;74 topologysort();75 printf("%d",ans);76 return 0;77 }
P2149 [SDOI2009]Elaxia的路线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。