QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56964#3893. Family FaresMahmoudAtiaAC ✓114ms8152kbC++2.2kb2022-10-22 07:34:482022-10-22 07:34:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-22 07:34:51]
  • 评测
  • 测评结果:AC
  • 用时:114ms
  • 内存:8152kb
  • [2022-10-22 07:34:48]
  • 提交

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, -1, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 1, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 1005, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, m, p, g, idx[N], dis[N][N], vis[N][N];
vector<pair<int, int> > v[N];

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[s][i] = oo;
    dis[s][s] = 0;
    priority_queue<pair<int, ll>> q;
    q.push({0, s});
    while (!q.empty()) {
        int node = q.top().second;
        ll cost = -q.top().first;
        q.pop();
        if (cost != dis[s][node]) continue;
        for (auto x:v[node]) {
            if (dis[s][x.first] > x.second + dis[s][node]) {
                dis[s][x.first] = x.second + dis[s][node];
                q.push({-dis[s][x.first], x.first});
            }
        }
    }
}

void build(int s, int node) {
    vis[s][node] = 1;
    for (auto x:v[node]) {
        if (dis[1][node] == dis[1][x.first] + x.second && !vis[s][x.first]) {
            build(s, x.first);
        }
    }
}

//#define endl '\n'
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("farm.in", "r", stdin);
    //memset(dp, -1, sizeof dp);
    cin >> n >> m >> p >> g;
    for (int i = 1; i <= p; i++) cin >> idx[i];
    while (m--) {
        int x, y, c;
        cin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    dijkstra(1);
    for (int i = 1; i <= p; i++) dijkstra(idx[i]);
    for (int i = 1; i <= p; i++) build(idx[i], idx[i]);
    ll ans = oo;
    for (int i = 1; i <= n; i++) {
        ll tmp = 0;
        for (int j = 1; j <= p; j++) {
            if (vis[idx[j]][i]) tmp += min(dis[idx[j]][1], g + dis[idx[j]][i]);
            else tmp += dis[idx[j]][1];
        }
        ans = min(ans, tmp);
    }
    cout << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3564kb

input:

6 5 3 10
4 5 6
1 2 10
2 3 10
3 4 10
4 5 2
4 6 3

output:

35

result:

ok single line: '35'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

7 7 4 10
5 4 4 7
1 2 100
2 3 100
3 4 10
1 5 80
3 5 30
3 6 10
6 7 5

output:

145

result:

ok single line: '145'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

4 5 2 10
2 4
1 2 20
2 4 5
1 3 20
3 4 5
1 4 30

output:

25

result:

ok single line: '25'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

1000 999 100 1000000
100 100 100 100 100 100 100 100 100 100 200 200 200 200 200 200 200 200 200 200 300 300 300 300 300 300 300 300 300 300 400 400 400 400 400 400 400 400 400 400 500 500 500 500 500 500 500 500 500 500 600 600 600 600 600 600 600 600 600 600 700 700 700 700 700 700 700 700 700 700...

output:

9000000000

result:

ok single line: '9000000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

1000 999 100 1000000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 500 500 500 500 500 500 500 5...

output:

25000000000

result:

ok single line: '25000000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

17 25 3 1
10 13 16
1 2 10
1 3 11
1 4 10
1 5 11
1 6 10
1 7 11
1 8 10
3 9 1
3 11 1
5 12 1
5 14 1
7 15 1
7 17 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
9 10 1
10 11 1
12 13 1
13 14 1
15 16 1
16 17 1

output:

21

result:

ok single line: '21'

Test #7:

score: 0
Accepted
time: 110ms
memory: 7776kb

input:

1000 100000 100 100
293 528 548 695 317 198 352 246 829 557 924 115 402 617 885 749 503 215 628 997 751 360 390 819 854 674 154 707 759 430 974 534 796 377 95 692 280 350 897 366 445 488 827 702 212 903 840 62 567 202 568 235 895 257 147 266 939 954 243 268 874 120 243 505 158 346 218 31 543 44 612 ...

output:

114214

result:

ok single line: '114214'

Test #8:

score: 0
Accepted
time: 112ms
memory: 7764kb

input:

1000 100000 100 100
943 95 543 177 813 98 407 370 673 722 118 813 589 820 225 520 67 736 240 761 316 896 226 783 843 103 991 188 248 1 921 138 914 943 770 566 914 366 320 905 301 791 130 35 157 775 773 365 288 698 815 631 909 182 211 851 603 386 802 728 86 32 602 143 819 560 706 842 390 660 969 272 ...

output:

120042

result:

ok single line: '120042'

Test #9:

score: 0
Accepted
time: 100ms
memory: 8044kb

input:

1000 100000 100 100
809 89 563 436 679 116 788 448 735 668 982 288 249 988 216 847 927 251 669 335 341 56 500 677 128 637 800 492 333 314 714 265 328 184 535 489 353 526 615 823 390 466 108 770 330 697 234 22 785 542 342 516 190 414 609 960 488 812 617 316 682 742 351 180 896 634 534 546 616 694 148...

output:

109852

result:

ok single line: '109852'

Test #10:

score: 0
Accepted
time: 102ms
memory: 7948kb

input:

1000 100000 100 100
890 865 592 567 373 674 212 163 140 783 564 877 882 643 161 704 981 538 803 238 219 723 282 839 1 765 602 146 802 130 151 121 649 434 772 353 598 499 515 658 491 438 520 446 127 590 556 227 539 528 1 87 30 64 114 559 6 308 279 108 587 752 553 846 17 840 995 642 621 341 235 719 40...

output:

82831

result:

ok single line: '82831'

Test #11:

score: 0
Accepted
time: 114ms
memory: 7768kb

input:

1000 100000 100 100
336 631 322 859 639 794 943 87 533 118 615 863 602 187 359 354 173 995 222 898 476 421 375 891 156 88 363 151 559 534 916 949 897 118 741 146 678 989 879 601 12 923 962 36 371 58 871 242 709 420 532 443 800 596 399 519 728 403 69 104 861 361 359 265 914 648 62 393 126 946 139 346...

output:

77320

result:

ok single line: '77320'

Test #12:

score: 0
Accepted
time: 109ms
memory: 7704kb

input:

1000 100000 100 100
299 960 207 310 730 682 579 371 690 684 240 937 937 949 153 802 157 475 202 794 584 997 982 938 222 578 376 343 487 208 836 760 740 409 452 8 409 872 893 651 80 502 514 476 111 642 579 982 253 730 879 780 858 279 19 859 666 8 213 629 495 22 76 259 723 969 292 979 417 543 87 914 9...

output:

144642

result:

ok single line: '144642'

Test #13:

score: 0
Accepted
time: 107ms
memory: 7964kb

input:

1000 100000 100 100
247 715 646 608 591 706 647 79 631 397 694 859 842 899 812 16 642 27 647 84 322 434 338 202 435 423 430 729 793 207 348 732 326 766 871 431 112 866 931 730 903 603 970 119 171 182 460 847 816 393 153 476 883 590 531 231 723 427 185 383 770 63 363 65 9 778 634 929 717 908 475 950 ...

output:

78259

result:

ok single line: '78259'

Test #14:

score: 0
Accepted
time: 91ms
memory: 7772kb

input:

1000 100000 100 100
652 667 28 821 67 895 720 861 531 249 796 135 776 45 41 274 854 887 500 297 585 839 187 43 77 547 696 819 282 854 446 176 785 185 924 530 747 437 382 904 393 560 77 716 122 428 425 509 959 602 886 18 715 415 629 688 764 607 869 706 371 126 71 712 349 889 978 500 183 790 666 209 1...

output:

82472

result:

ok single line: '82472'

Test #15:

score: 0
Accepted
time: 113ms
memory: 7764kb

input:

1000 100000 100 1
439 407 181 938 887 498 640 646 24 64 46 838 292 509 328 422 218 177 378 636 721 896 326 316 296 993 816 199 204 512 314 792 949 871 860 916 330 414 458 123 52 293 350 202 583 485 180 994 860 519 257 477 860 773 443 87 776 42 956 676 24 931 813 691 606 339 399 692 171 436 268 375 6...

output:

121164

result:

ok single line: '121164'

Test #16:

score: 0
Accepted
time: 111ms
memory: 7704kb

input:

1000 100000 100 50
760 567 442 239 153 276 923 619 258 112 914 902 184 316 391 171 719 184 498 801 984 410 799 812 271 353 245 444 330 533 590 69 207 882 964 720 579 231 96 794 36 903 581 853 562 714 337 9 888 454 27 337 409 321 887 578 459 614 173 701 875 709 5 460 262 25 99 607 558 685 59 310 73 1...

output:

120303

result:

ok single line: '120303'

Test #17:

score: 0
Accepted
time: 99ms
memory: 7900kb

input:

1000 100000 100 150
976 613 833 948 523 341 502 382 194 590 751 999 585 776 100 17 83 614 322 437 341 150 78 261 701 249 523 951 377 272 961 229 360 314 38 982 789 717 136 415 455 352 104 822 63 513 111 668 637 179 465 932 156 428 949 262 697 147 872 808 918 592 706 991 484 239 364 270 60 85 750 496...

output:

80531

result:

ok single line: '80531'

Test #18:

score: 0
Accepted
time: 107ms
memory: 7936kb

input:

1000 100000 100 250
285 687 187 864 721 465 299 404 662 763 825 460 136 808 390 771 457 781 379 438 359 520 160 415 921 532 386 613 61 1000 13 138 403 611 297 704 236 70 777 944 384 528 167 860 260 345 681 523 794 352 874 432 332 277 921 291 965 808 833 308 104 553 982 898 776 440 161 568 994 776 25...

output:

112414

result:

ok single line: '112414'

Test #19:

score: 0
Accepted
time: 109ms
memory: 8064kb

input:

1000 100000 100 500
539 179 7 37 331 106 182 284 630 784 970 306 344 651 666 914 726 989 181 382 698 136 836 961 887 684 324 622 26 722 250 690 809 493 683 595 98 256 170 819 623 303 772 250 855 360 336 400 660 692 495 303 146 94 77 811 687 809 286 154 761 641 301 635 551 204 778 31 34 183 159 898 7...

output:

117962

result:

ok single line: '117962'

Test #20:

score: 0
Accepted
time: 98ms
memory: 7788kb

input:

1000 100000 100 1000
978 253 556 553 505 580 549 443 345 575 608 876 383 24 322 782 601 464 326 899 965 779 202 454 682 753 984 251 621 175 603 525 751 709 327 443 561 661 924 233 33 564 408 134 303 190 502 928 79 189 530 611 620 841 860 358 556 305 354 672 486 666 435 953 765 756 181 574 682 695 86...

output:

104626

result:

ok single line: '104626'

Test #21:

score: 0
Accepted
time: 96ms
memory: 7836kb

input:

1000 100000 100 10000
459 594 457 260 460 271 605 467 979 184 101 817 101 388 171 397 646 95 373 98 916 165 455 435 34 324 379 660 256 531 199 29 339 836 328 806 276 19 47 611 683 843 31 693 251 55 326 940 690 679 971 995 353 859 488 468 424 861 326 891 550 414 349 949 137 710 148 357 13 454 452 163...

output:

215706

result:

ok single line: '215706'

Test #22:

score: 0
Accepted
time: 7ms
memory: 5772kb

input:

1000 999 100 100
256 230 58 526 754 353 707 620 250 625 967 679 742 465 41 849 333 194 651 65 495 629 111 13 54 941 890 453 749 249 758 469 759 924 760 579 188 906 669 428 658 392 515 337 565 162 631 383 127 25 595 39 275 741 877 498 109 507 621 76 24 225 873 415 508 184 902 607 768 707 699 172 418 ...

output:

137977

result:

ok single line: '137977'

Test #23:

score: 0
Accepted
time: 5ms
memory: 5868kb

input:

1000 999 100 100
7 507 7 310 279 339 844 699 492 266 247 487 1 885 26 876 836 638 679 891 638 400 98 183 455 283 444 103 37 198 221 762 762 399 705 316 596 314 990 940 126 479 620 840 201 398 155 173 290 520 720 681 229 290 526 511 788 852 690 41 157 740 898 865 867 463 136 270 10 1000 418 944 613 4...

output:

938871

result:

ok single line: '938871'

Test #24:

score: 0
Accepted
time: 10ms
memory: 5800kb

input:

1000 999 100 100
885 383 160 844 645 780 694 383 327 294 686 401 617 638 703 61 766 754 379 783 275 160 837 962 181 455 538 336 153 143 742 150 170 333 998 502 842 646 571 833 801 213 80 832 888 180 189 955 122 441 204 690 84 265 175 495 962 378 450 647 973 549 677 858 423 814 274 109 556 81 110 103...

output:

2218898

result:

ok single line: '2218898'

Test #25:

score: 0
Accepted
time: 10ms
memory: 5868kb

input:

1000 999 100 100
695 784 12 517 767 783 571 167 191 222 749 91 152 621 131 247 284 447 534 715 198 205 455 656 38 876 411 58 317 492 418 541 912 172 444 833 857 85 465 949 397 42 391 386 432 824 498 112 723 786 578 624 120 787 491 798 854 733 414 970 794 562 559 196 65 51 229 215 939 976 707 45 575 ...

output:

12194774

result:

ok single line: '12194774'

Test #26:

score: 0
Accepted
time: 107ms
memory: 7816kb

input:

1000 100000 100 100
329 443 153 222 750 410 625 483 581 126 346 631 117 5 645 126 812 375 160 93 366 195 99 481 378 962 608 876 39 999 542 700 412 628 889 926 289 248 833 444 182 7 252 568 566 342 762 885 240 209 289 250 722 990 228 16 979 302 430 484 372 201 936 742 4 579 800 675 125 174 61 905 360...

output:

120601

result:

ok single line: '120601'

Test #27:

score: 0
Accepted
time: 105ms
memory: 7808kb

input:

1000 100000 100 1000
333 590 139 542 153 581 271 580 571 998 281 793 241 455 135 76 459 371 129 496 404 575 794 88 802 999 958 766 456 587 109 768 755 669 46 731 413 153 953 508 576 225 128 776 422 883 179 689 577 141 807 84 849 873 806 807 921 835 782 108 21 137 117 242 316 263 379 594 601 526 937 ...

output:

8725653

result:

ok single line: '8725653'

Test #28:

score: 0
Accepted
time: 113ms
memory: 7768kb

input:

1000 100000 100 10000
289 409 63 132 483 894 716 424 456 765 267 992 184 531 693 522 590 379 903 473 935 748 779 187 244 401 243 267 68 80 594 911 722 223 324 331 178 842 832 238 849 615 747 71 350 773 294 658 379 887 384 2 210 301 206 760 440 290 76 483 457 313 815 622 159 656 732 768 997 131 708 5...

output:

9314777

result:

ok single line: '9314777'

Test #29:

score: 0
Accepted
time: 6ms
memory: 5584kb

input:

1000 999 100 250
14 25 33 35 42 43 49 68 82 87 94 101 108 118 129 174 189 193 195 197 206 209 212 215 240 261 270 273 275 280 287 298 299 311 358 363 365 371 373 381 389 410 419 435 454 467 468 474 483 486 492 493 496 520 542 552 572 596 604 607 608 617 619 647 657 664 684 706 719 729 731 745 747 76...

output:

35134

result:

ok single line: '35134'

Test #30:

score: 0
Accepted
time: 3ms
memory: 5672kb

input:

1000 999 100 123
12 27 31 36 42 57 64 70 72 83 109 120 121 125 130 161 164 166 172 184 193 207 209 226 228 233 245 251 256 264 267 278 322 329 336 341 353 369 380 381 391 410 416 417 420 429 471 473 474 478 482 496 510 523 526 527 545 547 561 570 576 586 603 605 608 613 659 679 688 693 697 699 701 7...

output:

29772

result:

ok single line: '29772'

Test #31:

score: 0
Accepted
time: 2ms
memory: 5100kb

input:

500 499 100 250
7 15 20 28 35 40 42 43 52 54 59 60 66 68 78 82 85 99 106 112 116 122 126 129 138 145 149 154 161 166 167 169 174 185 193 205 208 217 220 236 240 242 243 252 255 256 258 265 284 290 299 300 305 306 307 310 315 319 322 324 331 334 337 339 340 343 354 355 364 366 367 371 377 382 386 390...

output:

22803

result:

ok single line: '22803'

Test #32:

score: 0
Accepted
time: 4ms
memory: 3852kb

input:

1000 999 100 1000000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000...

output:

100000000

result:

ok single line: '100000000'

Test #33:

score: 0
Accepted
time: 90ms
memory: 8152kb

input:

1000 100000 100 1000000
723 374 406 15 774 152 208 604 616 278 970 527 262 783 399 908 374 11 124 683 303 665 178 412 852 59 245 94 703 559 151 192 777 82 463 550 89 253 725 876 857 222 195 676 957 422 372 349 169 905 82 360 710 607 437 122 929 769 300 93 958 679 433 59 4 946 317 351 1000 838 865 68...

output:

114693179

result:

ok single line: '114693179'

Test #34:

score: 0
Accepted
time: 9ms
memory: 5188kb

input:

1000 10000 50 1000000
516 883 845 416 215 758 866 206 554 433 504 41 790 825 802 527 452 831 689 72 772 97 117 629 673 602 553 240 207 468 978 542 266 701 770 895 989 379 646 692 769 532 586 743 875 946 649 747 639 888
868 811 432357
585 599 795828
687 633 827558
261 838 534298
563 605 765075
104 55...

output:

475605434

result:

ok single line: '475605434'

Test #35:

score: 0
Accepted
time: 97ms
memory: 7976kb

input:

1000 100000 100 100
966 212 792 934 922 513 276 325 239 84 331 665 804 290 431 664 775 646 462 187 594 778 277 250 335 245 417 105 924 103 70 552 895 696 661 211 21 810 347 515 511 395 717 757 378 519 696 244 668 269 493 314 240 752 314 919 136 249 517 300 323 267 253 297 933 632 263 910 679 179 310...

output:

99338

result:

ok single line: '99338'

Test #36:

score: 0
Accepted
time: 90ms
memory: 7948kb

input:

1000 100000 100 100
609 893 707 216 671 300 252 435 148 788 511 55 511 244 855 335 169 782 440 359 733 939 415 164 528 910 665 81 285 529 136 898 257 297 923 664 197 629 655 291 113 859 805 305 664 227 375 168 833 982 161 890 541 75 816 222 170 19 777 817 117 449 85 597 309 342 768 985 621 384 399 6...

output:

927278

result:

ok single line: '927278'

Test #37:

score: 0
Accepted
time: 99ms
memory: 7924kb

input:

1000 100000 100 500
847 835 736 511 836 654 677 306 546 321 388 354 55 713 153 745 971 76 12 974 766 804 906 10 133 696 710 384 114 432 621 900 663 930 179 506 377 524 683 761 590 276 296 730 417 271 7 71 947 513 130 673 304 314 512 335 541 27 692 139 623 642 867 622 380 991 250 5 228 113 818 215 86...

output:

7435099

result:

ok single line: '7435099'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

10 10 2 2
9 10
1 2 1
2 4 1
4 6 1
6 8 1
8 10 1
1 3 1
3 5 1
5 7 1
7 9 1
9 10 1

output:

5

result:

ok single line: '5'

Test #39:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

5 4 2 5
5 5
1 2 1
2 3 1
3 4 1
4 5 1

output:

8

result:

ok single line: '8'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

6 5 3 10
6 5 5
1 2 100
2 3 100
3 4 10
4 5 2
3 6 3

output:

57

result:

ok single line: '57'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

6 6 3 10
4 5 6
1 2 10
2 3 100
3 4 4
3 5 2
2 6 3
1 6 200

output:

39

result:

ok single line: '39'

Test #42:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

7 7 1 2
5
1 2 1
2 3 1
3 4 1
4 5 1
1 6 1
6 7 1
7 5 1

output:

2

result:

ok single line: '2'

Test #43:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

2 1 1 1
1
1 2 1

output:

0

result:

ok single line: '0'