社区讨论
求助求助。就过了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 条回复,欢迎继续交流。
正在加载回复...