oj.uz

답안 #562648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
562648 2022-05-14T21:13:44 Z Iwanttobreakfree 악어의 지하 도시 (IOI11_crocodile) C++
89 / 100
 492 ms 51780 KB 
#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;
typedef long long ll;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<pair<ll,ll>> d(N,{1e18,1e18});
    vector<bool> seen(N,false);
    vector<vector<pair<int,int>>> g(N,vector<pair<int,int>>());
    for(int i=0;i<M;i++){
        g[R[i][0]].push_back({R[i][1],L[i]});
        g[R[i][1]].push_back({R[i][0],L[i]});
    }
    priority_queue<pair<ll,int>> pq;
    for(int i=0;i<K;i++){
        pq.push({0,P[i]});
        //seen[P[i]]=true;
        d[P[i]].first=d[P[i]].second=0;
    }
    while(!pq.empty()){
        ll dist=-pq.top().first,u=pq.top().second;
        pq.pop();
        //cout<<u<<' ';
        if(dist!=d[u].second)continue;
        seen[u]=true;
        for(auto v:g[u]){
            if(seen[v.first])continue;
            if(dist+v.second<d[v.first].first){
                d[v.first].second=d[v.first].first;
                d[v.first].first=dist+v.second;
                pq.push({-d[v.first].second,v.first});
            }
            else if(dist+v.second<d[v.first].second){
                d[v.first].second=dist+v.second;
                pq.push({-d[v.first].second,v.first});
            }
        }
    }
    return d[0].second;
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 488 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 488 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 389 ms 43144 KB Output is correct
17 Correct 85 ms 13384 KB Output is correct
18 Correct 104 ms 14700 KB Output is correct
19 Correct 492 ms 51780 KB Output is correct
20 Correct 252 ms 34184 KB Output is correct
21 Correct 38 ms 5504 KB Output is correct
22 Incorrect 267 ms 30908 KB Output isn't correct
23 Halted 0 ms 0 KB -