HDU 2833 WuKong

WuKong

题意：

1.Alice从A走到B
2.Bob从C走到D
3.他们都会走最短路
4.问他们选的路最多有多少个公共点

解法:

1.n比较小可以floyd处理最短路
2.枚举交点，如果同时在两个最短路上就走下去
3.因为不能判断哪个状态会先更新，所以用spfa

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=305;
int n,m;
int s1,s2,t1,t2;
long long Dis[M][M],D1,D2;
int dis[M];
bool vis[M];
void spfa() {
    queue<int>Q;
    for(int i=1; i<=n; i++) {
        dis[i]=0;
        vis[i]=0;
        if(Dis[s1][i]+Dis[i][t1]==D1&&Dis[s2][i]+Dis[i][t2]==D2) {
            dis[i]=1;
            vis[i]=1;
            Q.push(i);
        }
    }
    while(!Q.empty()) {
        int x=Q.front();
        Q.pop();
        vis[x]=0;
        for(int i=1; i<=n; i++) {
            if(i==x)continue;
            if(Dis[s1][x]+Dis[x][i]+Dis[i][t1]==D1&&Dis[s2][x]+Dis[x][i]+Dis[i][t2]==D2) {
                dis[i]=dis[x]+1;
                if(!vis[i]) {
                    vis[i]=1;
                    Q.push(i);
                }
            }
        }
    }
}
int main() {
    int a,b,c;
    while(scanf("%d %d",&n,&m),n||m) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                Dis[i][j]=1e9;
            }
            Dis[i][i]=0;
        }
        for(int i=1; i<=m; i++) {
            scanf("%d %d %d",&a,&b,&c);
            Dis[a][b]=min(Dis[a][b],1ll*c);
            Dis[b][a]=Dis[a][b];
        }
        for(int k=1; k<=n; k++) {
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    if(Dis[i][k]+Dis[k][j]<Dis[i][j]) {
                        Dis[i][j]=Dis[i][k]+Dis[k][j];
                    }
                }
            }
        }
        scanf("%d %d %d %d",&s1,&t1,&s2,&t2);
        D1=Dis[s1][t1],D2=Dis[s2][t2];
        if(D1==1e9||D2==1e9) {
            printf("0\n");
            continue;
        }
        spfa();
        int ans=0;
        for(int i=1; i<=n; i++) {
            if(Dis[s1][i]+Dis[i][t1]==D1&&Dis[s2][i]+Dis[i][t2]==D2) {
                ans=max(ans,dis[i]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}