社区讨论

求助求助。就过了4个点

P1111修复公路参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo9832o3
此快照首次捕获于
2023/10/28 07:06
2 年前
此快照最后确认于
2023/10/28 07:06
2 年前
查看原帖
请问各位,为什么弗洛伊德算法会超时QAQ 就过了4个点QWQ
CPP
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>

using namespace std;
#define ll long long
#define endl '\n'

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline bool read(ll& x) {
    char c = getchar();
    
    while (c > '9' || c < '0')c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return true;
}

template<class T>void unwrite(T x) {
    if (x > 9) unwrite(x / 10);
    putchar(x % 10 + '0');
}

template<class T>inline void write(T x) {
    x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
}

template<class T>inline void write(T x, char&& c) {
    x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
    putchar(c);
}

ll n,m,x,y,A[1003][1003],i,j,k,inf=4e15;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    for(n=read(),m=read(),i=1;i<=n;++i)for(j=1;j<=n;++j)A[i][j]=inf;

    for(i=1;i<=n;++i)A[i][i]=0;

    for(;m>0;--m)x=read(),y=read(),A[x][y]=A[y][x]=min(A[x][y],read());

    for(k=1;k<=n;++k)for(i=1;i<=n;++i)for(j=1;j<=n;++j)
        A[i][j]=min(A[i][j],max(A[i][k],A[k][j]));

    for(i=1;i<=n;++i)for(j=1;j<=n;++j)A[0][0]=max(A[0][0],A[i][j]);

    write(A[0][0]==inf?-1:A[0][0],'\n');
}

回复

1 条回复,欢迎继续交流。

正在加载回复...