[Sdoi2009]Elaxia的路线

Time Limit:4000MS  Memory Limit:65536K
Total Submit:3 Accepted:2
Case Time Limit:1000MS

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

3

Hint

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

Source

Day2
额。。看上去很吓人，实际上还是蛮水的。。
首先可以注意到公共的路径必然是一段。。然后找出所有可以同时出现在两个最短路的边，用Dp求出最长的链就OK了。。。
Code：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=1500;
using namespace std;
int n,m,S[2],T[2];
struct Edge
{
int t,c;Edge*next;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxn]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
}
int DistS[2][maxn],DistT[2][maxn];
struct Queue
{
int Q[maxn],h,t;bool inQ[maxn];
Queue(){h=t=0;memset(inQ,0,sizeof(inQ));}
void inc(int&i){if(++i==maxn)i=0;}
void put(int x)
{
if(inQ[x])return;inQ[x]=true;
Q[t]=x;inc(t);
}
int get()
{
int tmp=Q[h];inc(h);inQ[tmp]=false;
return tmp;
}
bool empty(){return h==t;}
};
void Spfa(int vs,int Dist[maxn])
{
static Queue Q;
rep(i,n)Dist[i]=inf;Dist[vs]=0;Q.put(vs);
while(!Q.empty())
{
int t=Q.get(),c=Dist[t];
for(Edge*e=E[t];e;e=e->next)
if(c+e->c<Dist[e->t])
Dist[e->t]=c+e->c,Q.put(e->t);
}
}
int D[2];
bool inPath(int v)
{
rep(i,2)if(DistS[i][v]+DistT[i][v]!=D[i])return false;
return true;
}
bool inPath(int s,Edge*e)
{
rep(i,2)
{
int Dist=min(DistS[i][s]+DistT[i][e->t],DistS[i][e->t]+DistT[i][s])+e->c;
if(Dist!=D[i])return false;
}
return true;
}
bool In[maxn]={};
int A[maxn],v=0,Dp[maxn]={};
bool cmp(int i,int j)
{
return DistS[0][i]<DistS[0][j];
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d%d%d%d%d",&n,&m,S+0,T+0,S+1,T+1);int s,t,c;
rep(i,2)S[i]–,T[i]–;
while(m–)scanf("%d%d%d",&s,&t,&c),–s,–t,AddEdge(s,t,c);
rep(i,2)Spfa(S[i],DistS[i]),Spfa(T[i],DistT[i]);
rep(i,2)D[i]=DistS[i][T[i]];
rep(i,n)In[i]=inPath(i),In[i]?A[v++]=i:0;
sort(A,A+v,cmp);
int ans=0;
rep(i,v)
{
int t=A[i];ans>?=Dp[t];
for(Edge*e=E[t];e;e=e->next)if(In[e->t]&&inPath(t,e))
Dp[e->t]>?=Dp[t]+e->c;
}
cout<<ans<<endl;
}