BZOJ1880:[SDOI2009]Elaxia的路线(最短路,拓扑排序)

Description

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

Input

第一行：两个整数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。出出出格格格式式式：：：一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。

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

HINT

对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。

Solution

数组开小了WA,开大了MLE……emmm
四个点每个点spfa各跑一边最短路，
然后选定以一个人为标准重新建图
怎么建呢？枚举每个边，判断其在不在最短路内就好了
做题的时候忘了很不应该，CF的时候还做过一个类似的判断边是否在最短路上的题
注意要建单向边
然后拓扑排序求最长链，那么这个链就是两人最短路的最长相交了。

Code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<queue>
  5 #define N (1500+10)
  6 #define M (500000+10)
  7 using namespace std;
  8 struct node
  9 {
 10     int to,next,len;
 11 } edge[M*2];
 12 int head[N],num_edge;
 13 int n,m,x1,x2,y1,y2,len,p,ans;
 14 int u[M],v[M],l[M],Ind[N],dis[N];
 15 int disx1[N],disx2[N],disy1[N],disy2[N],used[N];
 16 queue<int>q;
 17 
 18 void add(int u,int v,int l)
 19 {
 20     edge[++num_edge].to=v;
 21     edge[num_edge].next=head[u];
 22     edge[num_edge].len=l;
 23     head[u]=num_edge;
 24 }
 25 
 26 void Spfa(int s,int *dis)
 27 {
 28     dis[s]=0;
 29     used[s]=true;
 30     q.push(s);
 31     while (!q.empty())
 32     {
 33         int x=q.front();
 34         q.pop();
 35         for (int i=head[x]; i; i=edge[i].next)
 36             if (dis[x]+edge[i].len<dis[edge[i].to])
 37             {
 38                 dis[edge[i].to]=dis[x]+edge[i].len;
 39                 if (!used[edge[i].to])
 40                 {
 41                     used[edge[i].to]=true;
 42                     q.push(edge[i].to);
 43                 }
 44             }
 45         used[x]=false;
 46     }
 47 }
 48 
 49 void Toposort()
 50 {
 51     for (int i=1; i<=n; ++i)
 52         if (!Ind[i]) q.push(i);
 53     while (!q.empty())
 54     {
 55         int x=q.front();
 56         q.pop();
 57         for (int i=head[x]; i; i=edge[i].next)
 58         {
 59             Ind[edge[i].to]--;
 60             dis[edge[i].to]=max(dis[edge[i].to],dis[x]+edge[i].len);
 61             ans=max(ans,dis[edge[i].to]);
 62             if (!Ind[edge[i].to])
 63                 q.push(edge[i].to);
 64         }
 65     }
 66 }
 67 
 68 int main()
 69 {
 70     scanf("%d%d",&n,&m);
 71     scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 72     for (int i=1; i<=m; ++i)
 73     {
 74         scanf("%d%d%d",&u[i],&v[i],&l[i]);
 75         add(u[i],v[i],l[i]);
 76         add(v[i],u[i],l[i]);
 77     }
 78     memset(disx1,0x7f,sizeof(disx1));
 79     memset(disy1,0x7f,sizeof(disy1));
 80     memset(disx2,0x7f,sizeof(disx2));
 81     memset(disy2,0x7f,sizeof(disy2));
 82     Spfa(x1,disx1);
 83     Spfa(x2,disx2);
 84     Spfa(y1,disy1);
 85     Spfa(y2,disy2);
 86 
 87     memset(edge,0,sizeof(edge));
 88     memset(head,0,sizeof(head));
 89     num_edge=0;
 90 
 91     for (int i=1; i<=m; ++i)
 92     {
 93         int len1=min(disx1[u[i]],disx1[v[i]]) + l[i] + min(disy1[u[i]],disy1[v[i]]);
 94         int len2=min(disx2[u[i]],disx2[v[i]]) + l[i] + min(disy2[u[i]],disy2[v[i]]);
 95         if (len1!=disx1[y1] || len2!=disx2[y2]) continue;
 96         if (disx1[u[i]]<disx1[v[i]]) add(u[i],v[i],l[i]),Ind[v[i]]++;
 97         else  add(v[i],u[i],l[i]),Ind[u[i]]++;
 98     }
 99     Toposort();
100     printf("%d",ans);
101 }