QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135664#3871. Voting CitiesWawi#0 51ms9824kbC++201.7kb2023-08-05 20:54:582024-07-04 01:17:46

Judging History

This is the latest submission verdict.

  • [2024-07-04 01:17:46]
  • Judged
  • Verdict: 0
  • Time: 51ms
  • Memory: 9824kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 20:54:58]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct cp
{
    bool operator()(pair<int,int> a,pair<int,int> b){
        return a.second > b.second; // Changed to '>' for min-heap behavior
    }
};

void solve(){
    int n,m,k; cin >> n >> m >> k;
    vector<int> go(k);
    for(int i=0; i < k;i++) cin >> go[i];
    vector<vector<pair<int,int>>> arr(n+1);
    for(int i=0; i < m;i++){
        int l,r,c; cin >> l >> r >> c;
        arr[l].push_back({r,c});
        arr[r].push_back({l,c});
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, cp> pq; // Changed to min-heap
    int q; cin >> q;
    while(q--){
        int s; cin >> s;
        int temp; cin >> temp >> temp >> temp >> temp >> temp;
        ll ans=0;
        if(s==go[0]){
            cout << 0 << endl;
            continue;
        }
        vector<bool> found(n+1);
        for(auto c: arr[s]){
            pq.push({c.first, c.second});
            found[s]=true;
        }
        
        found[s]=true;
        while(!pq.empty()){
            pair<int,int> c=pq.top();
            pq.pop();
            if(found[c.first]) continue;
            found[c.first]=true;
            if(c.first==go[0]){
                cout << c.second << endl;
                break;
            }
            for(auto g: arr[c.first]){
                if(found[g.first]) continue;
                pq.push({g.first, g.second+c.second});
            }
        }
        if(!found[go[0]]) cout << -1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    } 
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 4064kb

input:

5000 10000 1
4683
0 715 579327370
0 954 664830350
0 2453 244225980
0 2918 399241150
0 3929 982683290
1 4944 723915200
2 3725 390369490
3 1370 230814450
3 3348 750421430
3 3408 503334040
4 252 852709300
4 989 474431070
4 1013 466847840
4 4956 152207550
5 4162 271201150
6 3335 991911830
6 3596 4382854...

output:

46529694

result:

wrong answer 1st lines differ - expected: '7570531610', found: '46529694'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 42ms
memory: 9824kb

input:

5000 10000 1
939
0 1074 697931020
0 4334 347738890
1 2400 681303040
2 1685 896587820
2 2368 928896100
2 3133 12276450
2 3258 765661210
4 3606 993201320
5 1081 613705100
5 2339 700470170
5 2625 209307440
5 2832 129029550
7 1517 251821020
7 1751 713428320
7 2308 951691550
7 3980 498317440
7 4014 78197...

output:

232148044
260047664
571396634
577569474
703019194
713568554
824722864
857560854
894170124
927122894
939319994
1022548124
1038897594
1064923844
1082561914
1117944724
1121077234
1134485884
919375858
930308108
966212988
571638258
990792874
1145833464
-386927942
396577838
400791848
484587608
613998258
7...

result:

wrong answer 1st lines differ - expected: '5627552460', found: '232148044'

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 51ms
memory: 9216kb

input:

5000 10000 2000
366 1016 3277 5 3742 3640 2511 1725 2168 2349 1037 4972 2930 4374 3504 1098 3439 3970 1952 3474 2664 2097 1751 3679 3155 3266 2070 2016 338 1273 2648 4398 3694 2045 3524 1027 839 1898 1795 1192 2975 1756 4707 1548 4984 1891 2364 123 3181 1096 2970 3264 1628 1295 4852 829 4940 2251 37...

output:

-14909566
545165974
1170605804
82432604
183596924
412331724
757398354
972407264
1155131324
153831438
713906978
1020392268
746569322
651243592
1029562732
523857886
1043511286
999257510
-535265036
24810504
561945774
587555754
760019944
904148814
1009741904
1097017054
1137443584
1141121154
309141348
11...

result:

wrong answer 1st lines differ - expected: '0', found: '-14909566'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 3ms
memory: 4072kb

input:

5000 10000 1
4577
0 248 57534230
0 3020 827662530
0 3190 138424730
1 3154 752916230
4 1256 398736840
5 4116 833556610
5 4127 547494700
6 396 793865570
6 1661 388141660
7 4581 595148940
8 3768 724151300
9 1367 840320860
9 1656 391917460
10 3210 806346090
10 3356 767016610
10 3367 272248610
12 1145 72...

output:

1334070090

result:

wrong answer 1st lines differ - expected: '-1', found: '1334070090'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 34ms
memory: 8756kb

input:

5000 10000 200
1044 1225 1941 2497 4667 2566 3603 92 2261 1826 770 4780 127 4386 1948 2156 1504 4511 3119 4006 4473 389 3469 2670 3989 3092 55 670 4525 4965 1038 375 419 2599 4912 3665 4799 2997 4759 1660 1136 2308 1707 4249 3246 625 3378 52 734 4317 4958 3355 869 3361 2010 2300 2809 2635 2241 3441 ...

output:

-150102076
-123251266
-81862776
227303794
329399684
337497764
407774074
492350844
512837304
584614714
644739274
645765704
646725374
688221874
692151614
720394374
808901444
840764074
849933084
852383874
867491154
867785154
879046084
879514984
907478724
931504114
973258884
975873834
997724500
10231939...

result:

wrong answer 1st lines differ - expected: '-1', found: '-150102076'

Subtask #7:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 3ms
memory: 3848kb

input:

100 1000 10
98 30 76 47 68 72 37 62 38 78
0 40 955510110
0 58 380472040
0 67 471726660
0 75 21910230
0 76 203779460
0 79 619337400
0 92 789108960
0 95 850838250
1 7 708430
1 8 800979960
1 24 529606990
1 25 822365030
1 40 803087030
1 75 339182160
1 79 841073850
1 86 249876300
1 92 93708160
2 6 653731...

output:

31965470
209610240
185569060
195521840
209098370
202425800
234669040
88618840
171272390
232004510
245051090
245186480
246165220
182231390
144559570
191583910
169708900
203385240
160888710
117847240
175936700
218978170
219373540
224580380
132545750
228626840
56486000
162075330
203473500
215848080
210...

result:

wrong answer 1st lines differ - expected: '410099610', found: '31965470'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%