Just Look!

顶尖题目,说是在1000,其实可以用Floyd暴力解题:

嘉豪Floyd:

#include<iostream>
using namespace std;
int a[1005][1005],n,m,s;
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][k]<0x3f3f3f3f&&a[k][j]<0x3f3f3f3f){
                    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                a[i][j]=0x3f3f3f3f;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[u][v]=min(a[u][v],w);
    }
    floyd();
    for(int i=1;i<=n;i++){
        if(a[i][i]<0){
            printf("no solution");
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[s][i]>=0x3f3f3f3f/2){
            printf("-1 ");
        }
        else{
            printf("%d ",a[s][i]);
        }
    }
    return 0;
}