300网站建设,华星建设集团网站,深圳网站建设seo,北京软件开发工作室【BZOJ1880】[Sdoi2009]Elaxia的路线 Description 最近#xff0c;Elaxia和w**的关系特别好#xff0c;他们很想整天在一起#xff0c;但是大学的学习太紧张了#xff0c;他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间#xff0c;他…【BZOJ1880】[Sdoi2009]Elaxia的路线 Description 最近Elaxia和w**的关系特别好他们很想整天在一起但是大学的学习太紧张了他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间他们 希望在节约时间的前提下一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图地图上有N个路 口M条路经过每条路都需要一定的时间。 具体地说就是要求无向图中两对点间最短路的最长公共路径。 Input 第一行两个整数N和M含义如题目描述。 第二行四个整数x1、y1、x2、y21 ≤ x1 ≤ N1 ≤ y1 ≤ N1 ≤ x2 ≤ N1 ≤ ≤ N分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号两对点分别 x1,y1和x2,y2。 接下来M行每行三个整数u、v、l1 ≤ u ≤ N1 ≤ v ≤ N1 ≤ l ≤ 10000表 u和v之间有一条路经过这条路所需要的时间为l。 出出出格格格式式式 一行一个整数表示每天两人在一起的时间即最长公共路径的长度。 Output 一行一个整数表示每天两人在一起的时间即最长公共路径的长度 Sample Input 9 10 1 6 7 8 1 2 1 2 5 2 2 3 3 3 4 2 3 9 5 4 5 3 4 6 4 4 7 2 5 8 1 7 9 1 Sample Output 3 HINT 对于30%的数据N ≤ 100对于60%的数据N ≤ 1000对于100%的数据N ≤ 1500输入数据保证没有重边和自环。 题解先从x1,y1,x2都跑一边最短路这样我们就可以快速判断一条边是否在最短路上了。最后从y2跑最短路然后用f[x]表示从y2走到x时最长公共路径的长度。边最短路边DP即可。 然而好像被hack了。。。还是看大爷的题解吧。 #include cstring
#include cstdio
#include iostream
#include queue
#include utility
#define mp(A,B) make_pair(A,B)
using namespace std;
typedef pairint,int pii;
int n,m,cnt,S1,S2,T1,T2,la,lb;
int to[1000010],next[1000010],val[1000010],head[10010],dis[4][10010],vis[10010],f[10010];
priority_queuepii q;
inline int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-)f-f; gcgetchar();}while(gc0gc9) retret*10gc-0,gcgetchar();return ret*f;
}
void dijkstra(int S,int t)
{int i,u;memset(vis,0,sizeof(vis));dis[t][S]0,q.push(mp(0,S));while(!q.empty()){uq.top().second,q.pop();if(vis[u]) continue;vis[u]1;for(ihead[u];i!-1;inext[i]) if(dis[t][to[i]]dis[t][u]val[i])dis[t][to[i]]dis[t][u]val[i],q.push(mp(-dis[t][to[i]],to[i]));}
}
inline void add(int a,int b,int c)
{to[cnt]b,val[cnt]c,next[cnt]head[a],head[a]cnt;
}
int main()
{nrd(),mrd(),S1rd(),T1rd(),S2rd(),T2rd();int i,a,b,c,u,v;memset(head,-1,sizeof(head));for(i1;im;i) ard(),brd(),crd(),add(a,b,c),add(b,a,c);memset(dis,0x3f,sizeof(dis));dijkstra(S1,0),dijkstra(T1,1),dijkstra(S2,2),ladis[0][T1],lbdis[2][T2];memset(vis,0,sizeof(vis));dis[3][T2]0,q.push(mp(0,T2));while(!q.empty()){uq.top().second,q.pop();if(vis[u]) continue;vis[u]1;for(ihead[u];i!-1;inext[i]){vto[i];if(dis[3][v]dis[3][u]val[i]){dis[3][v]dis[3][u]val[i],f[v]0;q.push(mp(-dis[3][v],v));}if(dis[3][v]dis[3][u]val[i]){f[v]max(f[v],f[u]val[i]*((dis[1][u]dis[0][v]val[i]la||dis[0][u]dis[1][v]val[i]la)(dis[3][u]dis[2][v]val[i]lb||dis[2][u]dis[3][v]val[i]lb)));}}}printf(%d,f[S2]);return 0;
}//3 2 1 2 1 3 1 2 1 2 3 1 转载于:https://www.cnblogs.com/CQzhangyu/p/7560065.html
