QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #481222 | #603. 单源最短路径 | Sktn0089# | 100 ✓ | 2ms | 4356kb | C++14 | 850b | 2024-07-16 21:46:17 | 2024-07-16 21:46:18 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pir pair <ll, ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn = 1e4 + 10;
ll n, m, s, t, dis[maxn];
vector <pir> to[maxn];
priority_queue <pir> q;
int main(){
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for(ll i = 1; i <= m; i++) {
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
to[u].pb(mkp(v, w));
to[v].pb(mkp(u, w));
}
for(ll i = 1; i <= n; i++) dis[i] = 1e18;
dis[s] = 0, q.push(mkp(0, s));
while(!q.empty()) {
pir t = q.top(); q.pop();
ll d = -t.fi, u = t.se;
if(dis[u] ^ d) continue;
for(pir e: to[u]) {
ll v = e.fi, w = e.se;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(mkp(-dis[v], v));
}
}
}
printf("%lld", dis[t]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 4204kb
input:
7 11 5 4 2 4 2 1 4 3 7 2 2 3 4 3 5 7 5 7 3 3 6 1 1 6 3 4 2 4 3 5 6 3 7 2 1
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 10
Accepted
time: 0ms
memory: 4212kb
input:
10 20 9 4 5 6 308 8 10 696 4 2 569 8 6 471 1 2 874 5 3 130 4 5 804 8 9 89 10 4 717 10 9 41 7 6 998 1 6 639 7 9 650 7 8 339 3 1 597 9 1 622 7 10 2 5 1 4 1 4 372 1 10 163
output:
576
result:
ok 1 number(s): "576"
Test #3:
score: 10
Accepted
time: 0ms
memory: 4212kb
input:
20 43 11 19 8 14 569 17 13 859 11 14 571 18 14 583 14 5 569 9 1 342 14 6 397 14 17 640 12 1 331 19 12 999 16 1 203 19 6 493 9 14 645 7 4 118 15 6 218 15 20 164 13 16 737 1 15 548 1 17 478 4 15 286 4 17 964 12 14 165 15 7 759 1 5 976 19 11 491 15 11 286 14 1 889 10 17 852 15 16 6 20 3 563 12 7 538 11...
output:
491
result:
ok 1 number(s): "491"
Test #4:
score: 10
Accepted
time: 0ms
memory: 4152kb
input:
50 122 14 3 49 4 977 17 16 209 10 8 573 14 45 989 41 49 988 11 13 548 34 46 367 29 35 30 13 16 220 50 11 280 42 16 608 46 48 423 48 9 381 27 13 514 26 2 725 38 1 10 33 18 688 19 47 750 36 18 650 49 47 393 14 6 688 13 29 387 22 11 10 45 37 974 9 12 926 35 49 776 44 33 993 34 1 592 33 39 409 34 37 858...
output:
1215
result:
ok 1 number(s): "1215"
Test #5:
score: 10
Accepted
time: 1ms
memory: 4184kb
input:
100 251 88 95 90 39 170 75 71 718 38 37 51 92 86 622 29 46 790 85 43 175 14 65 614 2 97 123 72 28 919 9 89 158 63 89 159 55 30 297 76 4 267 94 93 56 96 85 293 69 65 539 58 49 281 85 14 997 98 15 693 72 39 73 90 47 513 100 53 642 96 28 897 14 73 790 26 14 289 90 52 699 91 84 283 56 32 480 71 24 151 9...
output:
969
result:
ok 1 number(s): "969"
Test #6:
score: 10
Accepted
time: 1ms
memory: 4168kb
input:
250 610 204 239 1 247 593 247 65 111 191 153 113 189 37 316 93 62 988 93 89 888 21 130 778 129 107 123 47 228 487 100 57 980 163 113 267 212 101 950 166 113 5 6 53 907 118 241 295 183 186 208 170 206 88 50 84 546 50 51 545 24 233 875 65 233 805 10 82 432 137 82 232 10 71 332 240 97 44 108 58 496 57 ...
output:
1544
result:
ok 1 number(s): "1544"
Test #7:
score: 10
Accepted
time: 1ms
memory: 4092kb
input:
500 1229 5 23 465 257 101 425 207 131 355 233 664 250 266 163 379 191 152 281 465 611 218 473 40 455 480 812 59 427 310 126 465 18 290 242 648 250 356 755 237 211 562 379 468 44 205 291 213 199 474 242 6 282 434 46 203 171 11 460 427 489 165 21 368 387 12 387 349 105 275 21 596 481 298 962 341 329 9...
output:
1252
result:
ok 1 number(s): "1252"
Test #8:
score: 10
Accepted
time: 0ms
memory: 4256kb
input:
1000 2450 925 987 674 703 724 780 787 532 101 418 143 102 463 431 103 481 109 104 496 854 105 497 593 106 507 493 107 508 875 565 789 511 800 565 119 108 578 499 255 9 123 872 862 1 745 991 369 788 373 241 277 987 124 278 382 125 291 601 126 387 332 127 366 72 128 378 511 129 369 389 210 799 798 42 ...
output:
762
result:
ok 1 number(s): "762"
Test #9:
score: 10
Accepted
time: 2ms
memory: 4300kb
input:
2000 4862 1935 306 1726 751 709 1643 1852 159 1388 1503 791 1881 1033 332 1360 1713 750 1656 1855 868 1439 573 758 1923 1333 593 1577 1742 112 105 1816 965 800 1560 130 10 1856 76 1735 1926 259 643 1902 301 1140 1301 475 580 180 860 1972 1236 383 238 722 242 1937 1372 282 1468 1316 95 64 522 696 132...
output:
1075
result:
ok 1 number(s): "1075"
Test #10:
score: 10
Accepted
time: 0ms
memory: 4356kb
input:
2500 6071 1760 669 2310 2380 17 2411 2373 371 2478 2411 405 2328 2492 300 538 2483 342 2310 2380 492 2262 2224 474 2202 2199 410 2215 2186 275 2154 2138 462 2186 2003 41 2121 2124 364 2029 2030 198 2125 1983 256 2042 2071 495 1895 1880 420 1862 1747 112 1963 1890 172 1890 1959 296 1926 1650 112 1651...
output:
1159
result:
ok 1 number(s): "1159"