题解：P11819 [PA 2019 Final] Floyd-Warshall

wwt100127 · 2025-03-10 18:24:36 · 题解

首先两点之间的距离用 n 次 Dijkstra 就可以了。

然后考虑什么样的边会被正确求出：

假设正在求 (x,y)：

• 若 x，y 间有边，则边权等于正常求法下的 dist_{x,y}。

• 存在一个点 p 使得 dist_{x,p} 和 dist_{p,y} 能正确求出，且在正常求法下 dist_{x,p} + dist_{p,y} = dist_{x,y}。

用 bitset 维护即可（代码中的 c_{i,j} 指的是从当前节点出发，i 为终点，j 是否可做“转移点”）。

#include<bits/stdc++.h>
#define int long long
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using namespace std;
using PII=pair<int,int>;
const int maxn=2e3+5;
const int maxm=2*maxn;
const int INF=0x3f3f3f3f3f3f3f3fll;
int n,m;

namespace Graph
{
    int head[maxn],tot_edge;
    struct edge
    {
        int v,w,next;
    }e[maxm];
    void G_init()
    {
        memset(head,-1,sizeof(head));
        tot_edge=-1;
    }
    void add(int u,int v,int w)
    {
        e[++tot_edge]=(edge){v,w,head[u]};
        head[u]=tot_edge;
    }
} using namespace Graph;

bitset<maxn> s[maxn],t[maxn],c[maxn];
int D[maxn][maxn];
int dist[maxn];
bool vis[maxn];
priority_queue<PII,vector<PII>,greater<PII> >q;
void Dijkstra(int s)
{
    int i;
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis)); 
    dist[s]=0; q.push(mp(0,s));
    while(q.size())
    {
        int x=q.top().se;
        q.pop();
        if(vis[x])
        continue;
        vis[x]=1;
        for(i=head[x];~i;i=e[i].next)
        {
            int y=e[i].v;
            if(dist[y]>dist[x]+e[i].w)
            {
                dist[y]=dist[x]+e[i].w;
                q.push(mp(dist[y],y));
            }
        }
    }
    for(i=1;i<=n;i++) D[s][i]=dist[i];
}
void GetC(int s)
{
    int i;
    for(i=1;i<=n;i++) c[i].reset();
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis)); 
    dist[s]=0; q.push(mp(0,s));
    while(q.size())
    {
        int x=q.top().se;
        q.pop();
        if(vis[x])
        continue;
        vis[x]=1;
        for(i=head[x];~i;i=e[i].next)
        {
            int y=e[i].v;
            if(dist[y]>dist[x]+e[i].w)
            {
                dist[y]=dist[x]+e[i].w;
                c[y]=c[x]; c[y][x]=1;
                q.push(mp(dist[y],y));
            }
            else
            if(dist[y]==dist[x]+e[i].w)
            {
                c[y]|=c[x];
                c[y][x]=1;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int i,j,u,v,w,x,y;
    cin>>n>>m;
    G_init();
    for(i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(i=1;i<=n;i++)
    Dijkstra(i);
    for(i=1;i<=n;i++)
    s[i][i]=t[i][i]=1;
    for(x=1;x<=n;x++)
    {
        for(i=head[x];~i;i=e[i].next)
        {
            int y=e[i].v;
            if(D[x][y]==e[i].w)
            s[x][y]=t[y][x]=1;
        }
    }
    for(x=1;x<=n;x++)
    {
        GetC(x);
        for(y=1;y<=n;y++)
        {
            if((s[x]&t[y]&c[y]).any())
            s[x][y]=t[y][x]=1;
        }
    }
    int ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        ans+=(D[i][j]<=INF/2 && !s[i][j]);
    }
    cout<<ans<<'\n';
    return 0;
}