QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377328 | #7995. 图 | Dva | WA | 2ms | 4432kb | C++14 | 2.3kb | 2024-04-05 12:32:31 | 2024-04-05 12:32:32 |
Judging History
answer
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define f(i, n, m) for (long long i = n; i <= m; ++i)
#define unf(i, n, m) for (long long i = n; i >= m; --i)
#define kong NULL
#define debug cout << "sss" << endl;
using ll = long long;
using ull = unsigned long long;
using point_t = double; // 计算几何的默认类型
const double e = exp(1.0);
const double pi = acos(-1.0);
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
constexpr ll maxx = 0x3f3f3f3f3f3f3f3f;
constexpr ll minn = 0xc0c0c0c0c0c0c0c0;
#define endl '\n'
constexpr char blank = ' ';
constexpr ll mod = (ll)998244353;
constexpr size_t N = (size_t)1e6 + 6;
#ifdef _DEBUG
#define Crash(...) (__debugbreak(), 0)
#define Debug(...) (__debugbreak(), 0)
#else
#define Crash(...) (exit(-1), 0)
#define Debug(...) ((void)0)
#endif // _DEBUG
#define ensure(expression) (void)(!!(expression) || Crash())
inline void setaccuracy(const std::streamsize &accuracy) {
std::cout << std::fixed << std::setprecision(accuracy);
}
#define int long long
using namespace std;
int n;
int mp[510][510];
int dp[510][510];
void bfs(int x,int fa,int wo){
vector<int>check(510,0);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>que;
que.push({0,x});
while(!que.empty()){
auto it=que.top();
que.pop();
if(check[it.second])continue;
check[it.second]=1;
f(i,1,n){
if(i==it.second)continue;
if(it.first+mp[it.second][i]<dp[wo][i]){
dp[wo][i]=it.first+mp[it.second][i];
dp[i][wo]=dp[i][wo];
que.push({dp[wo][i],i});
}
}
}
}
void solve() {
cin>>n;
f(i,1,n){
f(j,1,n){
cin>>mp[i][j];
dp[i][j]=maxx;
}
}
f(i,1,n)bfs(i,0,i);
int cnt=0;
f(i,1,n){
f(j,1,n){
if(i==j)dp[i][j]=0;
else if(dp[i][j]==mp[i][j]){
dp[i][j]=1;
}
else dp[i][j]=0;
}
}
f(i,1,n){
f(j,1,n)cout<<dp[i][j];
if(i!=n)cout<<endl;
}
// std::cout<< minn<<endl;
}
signed main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T = 1;
// cin >> T;
// scanf(" %d", &T);
// std::cin >> T;
// for (int q = 1; q <= T; q++) {
// while (T--) {
solve();
// }
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
4 0 3 2 100 3 0 8 100 2 8 0 10 100 100 10 0
output:
0110 1000 1001 0010
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 0 3 2 100 3 0 8 100 2 8 0 10 100 100 10 0
output:
0110 1000 1001 0010
result:
ok 4 lines
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 4432kb
input:
100 0 41659 61282 49636 67326 48035 29694 46438 87384 82143 38685 66540 48746 29800 91786 54931 56232 61941 53423 75707 45135 69244 53802 89998 64199 63778 75825 31745 66975 44537 35793 55663 72647 60768 80884 46657 54066 84568 6266 48213 78216 50369 66761 54861 67607 38509 52250 54210 71135 56840 5...
output:
0001000000000000000000000000000000000010010100000000100001001100101000000001000000000000000000010010 0011000000100000000001000000100000000000000000000000000000100000000001001000000001000000010000000100 01001000011000000000000000001000000000000000000000001000001011000010010010000000010000000100000001...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000001000000000000000000000010', found: '000100000000000000000000000000...0000001000000000000000000010010'