rockdu
题目描述
最近，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。
输出格式：
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）
输入输出样例
说明
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。
题目本身不难，但是偏码农。这道题我们先用SPFA找其中一个人所有的最短路，可以证明一定是一个DAG，用邻接矩阵存有向边。这个时候我们再跑一遍SPFA再建一个图，同样也一定是DAG，我们把涉及终点的最短路的有向边集建成图。再建一个图，将刚才那个图的边全部反向。然后我们对后两个图进行拓扑序+DP，如果当前点和枚举的点之间在第一个图中有连边则dp[u] = max(dp[u], dp[v] + 1)否则直接 dp[u] = max(dp[u], dp[v])正确性显然，代码量更显然，下面是代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<bitset>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1500 + 5;
struct edge {
int v, w, next;
}e[maxn * maxn * 4];
queue<pii > eq[maxn];
queue<int > pos, rev;
bool con[maxn][maxn];
bool vis[maxn];
int cnt, head[maxn], headg[maxn], headr[maxn], n, m, dis[maxn], p, dp[maxn];
int st1, st2, ed1, ed2, ans;
void adde(const int &u, const int &v, const int &w) {
e[++cnt] = (edge){v, w, head[u]};
head[u] = cnt;
}
void addg(const int &u, const int &v, const int &w) {
e[++cnt] = (edge){v, w, headg[u]};
headg[u] = cnt;
}
void addr(const int &u, const int &v, const int &w) {
e[++cnt] = (edge){v, w, headr[u]};
headr[u] = cnt;
}
int SPFA(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
queue<int > q;
q.push(s), vis[s] = 1, dis[s] = 0;
while(!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(dis[u] + e[i].w == dis[v])
eq[v].push(make_pair(u, e[i].w));
if(dis[u] + e[i].w < dis[v]) {
dis[v] = dis[u] + e[i].w;
while(!eq[v].empty()) eq[v].pop();
eq[v].push(make_pair(u, e[i].w));
if(!vis[v])
q.push(v), vis[v] = 1;
}
}
}
return dis[t];
}
void pre(int x) {
queue<int > q;
q.push(x);
while(!q.empty()) {
int u = q.front();q.pop();
while(!eq[u].empty()) {
q.push(eq[u].front().first);
con[eq[u].front().first][u] = 1;
eq[u].pop();
}
}
}
void Connect(int x) {
queue<int > q;
q.push(x);
while(!q.empty()) {
int u = q.front();q.pop();
while(!eq[u].empty()) {
q.push(eq[u].front().first);
if(!vis[u]) {
vis[u] = 1;
pos.push(u), pos.push(eq[u].front().first);
rev.push(u), rev.push(eq[u].front().first);
}
addg(eq[u].front().first, u, eq[u].front().second);
addr(u, eq[u].front().first, eq[u].front().second);
eq[u].pop();
}
}
}
void dfs(int u) {
vis[u] = 1;
for(register int i = headg[u]; i; i = e[i].next) {
if(!vis[e[i].v]) dfs(e[i].v);
if(con[u][e[i].v])
dp[u] = max(dp[e[i].v] + e[i].w, dp[u]);
else dp[u] = max(dp[u], 0);
ans = max(ans, dp[u]);
}
}
void dfs_rev(int u) {
vis[u] = 1;
for(register int i = headr[u]; i; i = e[i].next) {
if(!vis[e[i].v]) dfs_rev(e[i].v);
if(con[u][e[i].v])
dp[u] = max(dp[e[i].v] + e[i].w, dp[u]);
else dp[u] = max(dp[u], 0);
ans = max(ans, dp[u]);
}
}
void Topsort() {
memset(vis, 0, sizeof(vis));
while(!pos.empty()) {
int u = pos.front();
pos.pop();
if(vis[u]) continue;
dfs(u);
}
}
void Topsort_rev() {
memset(vis, 0, sizeof(vis));
while(!rev.empty()) {
int u = rev.front();
rev.pop();
if(vis[u]) continue;
dfs_rev(u);
}
}
int main() {
scanf("%d%d", &n, &m);
scanf("%d%d%d%d", &st1, &ed1, &st2, &ed2);
int u, v, w;
for(register int i = 1; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
adde(u, v, w), adde(v, u, w);
}
SPFA(st1, ed1);
pre(ed1);
for(register int i = 1; i <= n; ++i) {
while(!eq[i].empty()) eq[i].pop();
}
SPFA(st2, ed2);
memset(vis, 0, sizeof(vis));
Connect(ed2);
Topsort();
memset(dp, 0, sizeof(dp));
Topsort_rev();
printf("%d", ans);
return 0;
}
没有帐号? 立即注册