[BZOJ]Elaxia的路线[SDOI2009]

题目描述

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

输入输出格式

输入格式

第一行：两个整数N和M（含义如题目描述）。第二行：四个整数$$x_1、y_1、x_2、y_2（1 ≤ x_1 ≤ N，1 ≤ y_1 ≤ N，1 ≤ x_2 ≤ N，1 ≤ ≤ N）$$，分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 $$x_1,y_1$$和$$x_2,y_2$$）。接下来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+拓扑

四遍SPFA，然后判断每一条边是否可以在最短路中，是的话就新开一个图，在同一位置加入一条单向边，然后进行拓扑排序，维护答案最大值就好了。由于原题中两人面对面经过也同样算作可行方案，所以我们需要选择出允许两人面对面经过的可行最短路方案，再重新开一个图跑一遍拓扑排序，维护出答案就好了。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 15100;
const int inf = 0x3f;
int n, m, x1, y1, x2, y2;
int head[maxn], cnt = 0;
int Head[maxn];
struct node { int to, nxt, val; };
node e[3000010];
int dis1[maxn], tme1[maxn], dis2[maxn], tme2[maxn];
int tog[maxn];
int in[maxn];
queue<int>q;
int ans = 0;

inline int max(int a, int b) { return a > b ? a : b; }

void adde(int h[], int x, int y, int val)
{
    cnt++;
    e[cnt].to = y; e[cnt].nxt = h[x]; e[cnt].val = val; h[x] = cnt;
}

inline void SPFA(int S, int dis[])
{
    memset(dis, inf, sizeof(int) * 1510);
    dis[S] = 0; q.push(S);
    while (!q.empty())
    {
        int tmp = q.front(); q.pop();
        tog[tmp] = 0;
        for (int i = head[tmp]; i; i = e[i].nxt)
            if (dis[e[i].to]>dis[tmp] + e[i].val)
            {
                dis[e[i].to] = dis[tmp] + e[i].val;
                if (!tog[e[i].to]) tog[e[i].to] = 1, q.push(e[i].to);
            }
    }
}

void Topological()
{
    int dis[10000];
    memset(dis, 0, sizeof(dis));
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);
    while (!q.empty())
    {
        int tmp = q.front(); q.pop();
        ans = max(ans, dis[tmp]);
        for (int i = Head[tmp]; i; i = e[i].nxt)
        {
            dis[e[i].to] = max(dis[e[i].to], dis[tmp] + e[i].val);
            if (!--in[e[i].to]) q.push(e[i].to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    for (int i = 1; i <= m; i++)
    {
        int u, v, l;
        scanf("%d%d%d", &u, &v, &l);
        adde(head, u, v, l); adde(head, v, u, l);
    }
    SPFA(x1, dis1); SPFA(y1, tme1); SPFA(x2, dis2); SPFA(y2, tme2);
    for (int x = 1; x <= n; x++)
        for (int i = head[x]; i; i = e[i].nxt)
            if (dis1[x] + e[i].val + tme1[e[i].to] == dis1[y1] && dis2[x] + e[i].val + tme2[e[i].to] == dis2[y2])
                adde(Head, x, e[i].to, e[i].val), in[e[i].to]++;
    Topological();
    memset(Head, 0, sizeof(Head));
    for (int x = 1; x <= n; x++)
        for (int i = head[x]; i; i = e[i].nxt)
            if (dis1[x] + e[i].val + tme1[e[i].to] == dis1[y1] && dis2[e[i].to] + e[i].val + tme2[x] == dis2[y2])
                adde(Head, x, e[i].to, e[i].val), in[e[i].to]++;
    Topological();
    printf("%d\n", ans);
}

[BZOJ]Elaxia的路线