ETO的公开赛T3《寻星》 题解(BY 超級·考場WA怪 )

题解 寻星

题意：给定一个有向带权图，定义从一点到另一点的某条路径长为路径上所有边权的最大值，并给定四个点编号w，t1，t2，t3。

求出一个点s，使它在到t1，t2，t3三点最短路径最大值最大或者根本不存在路径的基础上，到w的最短路径最小。

思路：

本来是要加强数据卡Floyd，但也是来不及了，Floyd无脑跑一遍再枚举即可。注意这是个有向图，而且三体人也看作是人类。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define fp(i,a,b) for(int i=a;i<=b;++i)
int dis[900][900],n,m,w,t1,t2,t3,ans=-1,maxc=-1,minc=0x7fffffff;
int main()
{
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    fp(i,1,n)dis[i][i]=0; 
    fp(i,1,m){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        dis[x][y]=c;
    }
    fp(k,1,n)
        fp(i,1,n)
            fp(j,1,n)
                if(dis[i][j]>max(dis[i][k],dis[k][j]))
                    dis[i][j]=max(dis[i][k],dis[k][j]);
    scanf("%d%d%d%d",&w,&t1,&t2,&t3);
    fp(i,1,n){
        if(i==w||i==t1||i==t2||i==t3||dis[w][i]>=INF)continue;
        int dt=min(dis[t1][i],min(dis[t2][i],dis[t3][i]));
        if(dt>maxc){
            maxc=dt;
            ans=i;
        }
        else if(dt==maxc){
            if(dis[w][i]<minc){
                minc=dis[w][i];
                ans=i;
            }
        }
    }
    printf("%d",ans);
    return 0;
}