LYDSY 1880

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
#include <cstring>
inline int abs(int x) { return x >= 0 ? x : -1; }
inline int max(int a, int b) { return a > b ? a : b; }
int head[1510], next[1000010], to[1000010], len[1000010], ecnt, ans;
int disS1[1510], disS2[1510], disE1[1510], disE2[1510], que[1000010];
bool inq[1510];
inline void addEdge(int f, int t, int l)
{
    ecnt++;
    next[ecnt] = head[f];
    head[f] = ecnt;
    to[ecnt] = t;
    len[ecnt] = l;
}
void spfa(int s, int *dis)
{
    memset(inq, 0, sizeof(inq));
    int h, t, x;
    h = t = x = 0;
    for (dis[s] = 0, que[t++] = s, inq[s] = true; h ^ t; inq[que[h++]] = false)
        for (int cur = head[que[h]]; cur; cur = next[cur])
            if (dis[to[cur]] > dis[que[h]] + len[cur])
            {
                dis[to[cur]] = dis[que[h]] + len[cur];
                if (!inq[to[cur]]) que[t++] = to[cur], inq[to[cur]] = true;
            }
}
int main()
{
    memset(disS1, 0x3f3f3f3f, sizeof(disS1));
    memset(disS2, 0x3f3f3f3f, sizeof(disS2));
    memset(disE1, 0x3f3f3f3f, sizeof(disE1));
    memset(disE2, 0x3f3f3f3f, sizeof(disE2));
    int n, m, x1, y1, x2, y2;
    scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
    for (int i = 0, x, y, z; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
    }
    spfa(x1, disS1), spfa(x2, disS2), spfa(y1, disE1), spfa(y2, disE2);
    int len1 = disS1[y1], len2 = disS2[y2];
    for (int i = 1; i <= n; i++)
        if (disS1[i] + disE1[i] == len1 && disS2[i] + disE2[i] == len2)
            for (int j = 1; j <= n; j++)
                if (disS1[j] + disE1[j] == len1 && disS2[j] + disE2[j] == len2)
                    ans = max(ans, abs(disS1[i] - disS1[j]));
    printf("%d", ans);
    return 0;
}