QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414177 | #7995. 图 | Acetaminophen | AC ✓ | 278ms | 6676kb | C++11 | 1.4kb | 2024-05-18 16:26:53 | 2024-05-18 16:26:55 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505; // 假设最大节点数为105
int dist[N][N]; // 存储两点间最短距离
int s[N][N];
int ans[N][N];
void init() {
memset(dist, 0x3f, sizeof(dist)); // 将dist数组初始化为一个很大的数
for (int i = 1; i < N; i++) {
dist[i][i] = 0; // 自己到自己距离为0
}
for(int i = 1; i < N; i++)
{
for(int j = 1; j < N; j++)
ans[i][j] = 1;
}
for (int i = 1; i < N; i++) {
ans[i][i] = 0; // 自己到自己距离为0
}
}
int main() {
int n;
cin >> n;
init();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin>>x;
s[i][j]=x;
dist[i][j] = min(dist[i][j], x);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(dist[i][j] >= dist[i][k] + dist[k][j] && (k !=i && k !=j))
ans[i][j] = 0;
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << ans[i][j];
}
cout << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5632kb
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: 1ms
memory: 6480kb
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: 0
Accepted
time: 4ms
memory: 5876kb
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:
0000000000000000000000000000000000000010000100000000100001001000000000000001000000000000000000000010 0011000000100000000000000000000000000000000000000000000000100000000000000000000000000000000000000000 01001000010000000000000000000000000000000000000000001000000010000000000010000000010000000000000000...
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 6548kb
input:
100 0 81722 50546 79959 47292 51747 54712 7396 58005 52529 61319 66453 61823 76359 55454 60837 29465 61066 66711 75051 58395 38189 44176 32315 39742 46514 23229 27872 59119 39600 81204 45383 59424 40396 51094 74411 16551 30485 42587 18676 82697 76869 48206 41961 44633 59558 41795 57384 59943 18175 4...
output:
0000000100000000000000000000000000000000000000000100000000000001000000000000000100000000000000000000 0000000000000001010100000000000000000000000000000000000100000000001000000000000000000000000000000000 00000000001000001000000000001000000000000000000000000000000000000000100000001000000001000000000000...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 4ms
memory: 6592kb
input:
100 0 1 2 1 2 1 1 1 1 1 1 1 1 2 2 2 2 2 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 2 1 1 1 1 1 1 2 1 1 2 2 1 1 1 2 2 1 1 2 1 2 1 2 1 2 2 2 1 1 2 1 2 3 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 0 1 1 1 2 3 2 2 1 1 1 1 2 2 1 3 3 2 2 1 3 2 2 2 1 3 2 2 1 1 2 2 3 1 2 1 1 1 1 1 2 3 2 1 1 2 1 ...
output:
0101011111111000001000001101111111111001110111111011001110011010101000110100110001111011011111111011 1011100001111001000010000100011000101111100011010110000111101011101000010001010111011010111011101101 01000011010010010111101101101111110111110000101000101111100010110010011100110101101010100000110011...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 4ms
memory: 5824kb
input:
100 0 2 2 1 2 2 2 2 1 2 2 2 1 1 2 1 2 1 2 2 2 3 2 2 2 2 1 1 1 2 1 2 1 2 1 2 1 2 2 2 2 1 1 1 1 1 1 2 2 2 1 1 2 2 2 1 2 2 1 1 3 1 1 2 2 2 2 1 2 1 3 2 1 2 1 1 1 1 2 2 1 1 1 2 2 2 1 2 2 1 1 2 1 1 3 1 1 3 2 1 2 0 1 1 2 1 2 2 2 2 1 3 2 2 2 1 1 1 2 3 1 1 1 2 1 2 2 2 1 1 2 2 1 1 2 1 1 2 2 1 2 1 1 1 2 2 1 1 ...
output:
0001000010001101010000000011101010101000011111100011000100110110000101001011110011100010011011011001 0011010000100001110011101000110011011001011100110110101100010010000110100111100111111010101001011011 01010001110101001110100011100011010010110000110001110101101010111001101010110001101110011101010111...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 165ms
memory: 6676kb
input:
500 0 743810 457854 85842 793418 318922 803556 939014 213357 346386 67230 841985 991820 600886 111369 198349 745203 809216 581207 443436 374000 684975 536767 444827 513284 841566 95714 870537 213411 507714 279089 852847 236477 266161 457883 432456 181558 6690 709759 89446 718063 263025 285303 124290...
output:
000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000...
result:
ok 500 lines
Test #8:
score: 0
Accepted
time: 146ms
memory: 6668kb
input:
500 0 2 2 8 1 5 10 7 6 9 5 9 2 4 8 6 5 3 1 3 3 10 7 1 7 9 10 9 6 6 9 2 8 9 10 10 1 5 5 9 6 5 8 8 6 5 6 2 3 3 10 10 8 4 10 9 6 6 6 6 2 9 6 5 4 3 7 8 6 1 6 4 1 9 5 8 9 2 7 6 8 1 1 8 7 7 4 3 5 10 4 1 8 1 6 9 6 6 10 8 8 10 1 10 4 9 2 4 5 5 4 4 8 1 3 8 8 4 1 8 1 8 3 8 2 6 2 4 9 2 10 7 9 1 10 9 7 1 4 1 9 ...
output:
000010000000000000100001000000000000100000000000000000000000000000000100100000000110000000010100000000100000000001000010100000000000010001010000100000000000000000000000000000010000000010000100000000101001000010000000000000010000100000000000000001100100000010000000000000010100000100000000000000000000...
result:
ok 500 lines
Test #9:
score: 0
Accepted
time: 130ms
memory: 6548kb
input:
500 0 14893 9715 8418 11689 7914 12453 6215 7449 8307 13288 8074 7145 7404 7035 6513 10885 7276 7395 9395 7329 6788 2571 11164 8363 6852 5689 3704 3170 13069 10644 6587 9992 8314 11542 8168 11649 8763 5142 7790 5867 5745 13489 9658 9898 6896 7174 4354 5776 9910 7437 6110 6612 4468 8756 2310 5397 982...
output:
000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000010000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010000000000000...
result:
ok 500 lines
Test #10:
score: 0
Accepted
time: 130ms
memory: 6576kb
input:
500 0 13216 9169 13904 1547 16781 11728 10087 14614 7941 15600 7706 20640 10377 12331 14186 9601 11270 13364 10161 10522 8487 11492 17192 12168 16538 9189 12061 10379 11223 9937 11564 6284 13004 7186 11204 14242 8111 6926 10945 12755 13084 4181 11593 11193 15592 15546 8845 9903 5180 14922 12151 9823...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000...
result:
ok 500 lines
Test #11:
score: 0
Accepted
time: 276ms
memory: 6588kb
input:
500 0 1 1 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 2 1 1 1 2 2 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 2 1 1 1 2 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 ...
output:
011110111010111111111100101110111000101011111111111111101110110110011111111101111110011101111011011011111011110111111110101111111011111011111111111011010011111111111110111011010111110110111101111011110101111010111111011011111110101100110110111111110110001110111111111111011111010110111001111101110101...
result:
ok 500 lines
Test #12:
score: 0
Accepted
time: 278ms
memory: 6672kb
input:
500 0 1 1 1 2 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 1 2 1 1 1 1 2 1 2 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 ...
output:
011101011101111111110101101111010111001111101111111101111111111100110101110111111111111101011111111001110011111011011110111111111111111111011111110111011101010110000011111110001111100011101110111111111100010111111110110011001001011111111011111011001111111010001111001111111111111111101111011111111110...
result:
ok 500 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 5700kb
input:
10 0 102903 762919 272795 596098 162724 539281 422480 972306 801029 102903 0 785142 527821 728512 58732 284056 151031 254112 357952 762919 785142 0 553216 749299 508759 222588 86457 513574 786813 272795 527821 553216 0 87749 960681 437647 636732 130825 109597 596098 728512 749299 87749 0 724079 8275...
output:
0101000000 1000010110 0000001100 1000100011 0001000001 0100001001 0010010001 0110000010 0101000100 0001111000
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 1ms
memory: 6616kb
input:
10 0 7 9 4 3 4 2 9 8 2 7 0 8 7 2 10 5 7 2 6 9 8 0 7 2 5 2 9 1 8 4 7 7 0 4 8 3 4 6 5 3 2 2 4 0 5 9 7 7 10 4 10 5 8 5 0 6 1 3 4 2 5 2 3 9 6 0 1 3 10 9 7 9 4 7 1 1 0 1 7 8 2 1 6 7 3 3 1 0 5 2 6 8 5 10 4 10 7 5 0
output:
0001101001 0000100011 0000101010 1000101001 1111000000 0000000101 1011000100 0000011010 0110000101 1101010010
result:
ok 10 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
10 0 296685 168853 311204 319321 30372 128773 43837 288294 163351 296685 0 207992 462792 358459 276600 167911 290065 248089 233204 168853 207992 0 334959 230628 183722 40079 170258 324272 332204 311204 462792 334959 0 104331 280831 294880 267368 243671 395251 319321 358459 230628 104331 0 334191 190...
output:
0000011001 0000011011 0000001010 0000100110 0001001011 1100000110 1110100100 0001011000 0111110000 1100100000
result:
ok 10 lines
Test #16:
score: 0
Accepted
time: 1ms
memory: 5560kb
input:
10 0 255405 365136 78527 279299 184302 23569 393021 503455 96085 255405 0 109884 333933 258565 154113 278975 151345 262196 177107 365136 109884 0 396524 148679 263998 341567 41460 372081 286992 78527 333933 396524 0 301040 262831 54957 437986 424927 174612 279299 258565 148679 301040 0 271432 302869...
output:
0100011101 1010010011 0100101100 0000101010 0011000001 1100000001 1011000000 1010000000 0101000000 1100110000
result:
ok 10 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 6640kb
input:
10 0 2 2 1 4 2 5 2 3 4 2 0 1 1 4 1 4 3 4 2 2 1 0 1 4 2 5 4 3 3 1 1 1 0 3 1 3 4 2 4 4 4 4 3 0 4 7 1 7 7 2 1 2 1 4 0 2 4 3 5 5 4 5 3 7 2 0 8 1 4 2 3 4 4 1 4 8 0 6 6 3 4 3 2 7 3 1 6 0 3 4 2 3 4 7 5 4 6 3 0
output:
0001000100 0011010101 0101000000 1110110010 0001000100 0101001000 0000010010 1100100000 0001001001 0100000010
result:
ok 10 lines
Test #18:
score: 0
Accepted
time: 1ms
memory: 5612kb
input:
10 0 3 2 4 7 2 4 4 1 3 3 0 1 2 6 2 2 1 4 1 2 1 0 1 5 4 1 1 3 2 4 2 1 0 4 2 1 2 3 3 7 6 5 4 0 7 3 7 6 6 2 2 4 2 7 0 4 3 1 4 4 2 1 1 3 4 0 2 4 3 4 1 1 2 7 3 2 0 4 1 1 4 3 3 6 1 4 4 0 4 3 1 2 3 6 4 3 1 4 0
output:
0010000011 0010010101 1101001100 0010011000 0000001010 0101000010 0011100000 0110000001 1000110000 1100000100
result:
ok 10 lines
Test #19:
score: 0
Accepted
time: 4ms
memory: 6676kb
input:
100 0 865652 854605 909735 164494 414229 602669 428535 122877 919971 459811 724310 433010 360455 877866 96067 562884 361529 104991 178519 197425 853689 354804 504557 80597 524908 793930 230611 405083 883465 798550 471732 228873 85005 374026 829605 197037 680285 873452 342258 619169 800620 129491 671...
output:
0000000000000000000000000000000001000000000000000000000000000000000000000000010001000100000010000100 0000000000000000000000010000000000000000010000000000000010000000000011000010000000000000000000000000 00000010001000000000000000000000000000000000000000000000000100000000001000000000000000000000000000...
result:
ok 100 lines
Test #20:
score: 0
Accepted
time: 4ms
memory: 5720kb
input:
100 0 2 6 7 2 6 8 2 10 6 7 2 10 4 4 8 2 6 4 3 8 3 9 1 2 5 4 1 10 10 3 10 5 7 9 6 2 6 10 10 1 8 4 7 2 5 8 8 3 9 4 3 9 4 4 8 3 10 1 5 6 4 6 9 9 9 8 1 8 5 3 6 5 9 10 5 9 3 6 8 8 9 5 3 9 2 3 4 9 3 7 10 8 8 7 3 6 9 5 10 2 0 10 4 4 10 9 4 3 8 8 6 2 4 9 7 1 4 2 10 3 1 1 6 10 3 2 4 7 1 3 10 4 9 10 9 9 6 2 7...
output:
0000100100010000100000011001000000000000100000000000000000100000000100000000000000000100000000000000 0000000000000000101001100000010000000000100000000100000000000011111000000000000001000010000001001000 00000000000000001000010000100001010100000101000000000001000100000000011010000010000000000000000100...
result:
ok 100 lines