oj.uz

Submission #562653

# Submission time Handle Problem Language Result Execution time Memory
562653 2022-05-14T21:24:27 Z Iwanttobreakfree Crocodile's Underground City (IOI11_crocodile) C++
0 / 100
 1 ms 340 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,ll>>> g(N,vector<pair<int,ll>>());
    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;
                if(d[v.first].first!=d[v.first].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;
}
/*int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int R[m][2],l[m],e[k];
    for(int i=0;i<m;i++)cin>>R[i][0]>>R[i][1]>>l[i];
    for(int i=0;i<k;i++)cin>>e[i];
    cout<<travel_plan(n,m,R,l,k,e);
}*/

Subtask #1
0 / 46.0

# Verdict Execution time Memory 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 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory 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 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory 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 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -