oj.uz

답안 #199748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199748 2020-02-03T06:19:38 Z shahriarkhan 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 6 ms 2680 KB 
#include<bits/stdc++.h>
using namespace std ;

#define pii pair<int,int>

const int mx = 1e5 + 5 , inf = 1e9 + 10 ;

vector<pii> adj[mx] ;

int dist[mx] , vis[mx] , ans[mx][2] ;

void djikstra(int n , int m , int r[][2] , int l[] , int k , int p[])
{
    for(int i = 0 ; i < n ; ++i) dist[i] = ans[i][0] = ans[i][1] = inf ;

    priority_queue<pii,vector<pii>,greater<pii> > pq ;

    for(int i = 0 ; i < k ; ++i)
    {
        pq.push({0,p[i]}) ;
        dist[p[i]] = ans[p[i]][0] = ans[p[i]][1] = 0 ;
    }

    while(!pq.empty())
    {
        pii pr = pq.top() ;
        pq.pop() ;
        int to = pr.second ;
        if(vis[to]) continue ;
        vis[to] = 1 ;
        int siz = adj[to].size() ;
        for(int i = 0 ; i < siz ; ++i)
        {
            int a = pr.first , b = pr.second ;
            int d = dist[to] + b ;
            if(d<=ans[a][0])
            {
                 ans[a][1] = ans[a][0] ;
                 ans[a][0] = d ;
                 dist[a] = ans[a][1] ;
                 pq.push({ans[a][1],a}) ;
            }
            else if(d < ans[a][1])
            {
                ans[a][1] = d ;
                dist[a] = d ;
                pq.push({d,a}) ;
            }
        }
    }
}

int travel_plan(int n , int m , int r[][2] , int l[] , int k , int p[])
{
    for(int i = 0 ; i < m ; ++i)
    {
        int a = r[i][0] , b = r[i][1] ;
        adj[a].push_back({b,l[i]}) ;
        adj[b].push_back({a,l[i]}) ;
    }
    djikstra(n,m,r,l,k,p) ;
    return ans[0][1] ;
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -