oj.uz

답안 #1013497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013497 2024-07-03T15:08:37 Z vjudge1 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 305 ms 73312 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pi>
#define pb push_back
#define INF 1e18
#define endl '\n'
//#define int ll
#define pii pair<pi,ll>

const int MAX = 1e5+1;

vpi g[MAX];
ll dis[MAX][2];


ll travel_plan(int n,int m, int R[][2], int L[],int k, int P[]){
    ll a,b,c,from;
    
    for(int i = 0; i < m; i++){
       a = R[i][0];
       b = R[i][1];
       c = L[i];
       g[a].pb({b,c});
       g[b].pb({a,c});
    }

    priority_queue<pi, vector<pi>, greater<pi>>pq;
     for(int i = 0; i < n; i++){
        dis[i][0]=INF;
        dis[i][1]=INF;
    }

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

   int vis[n];
   memset(vis,0,sizeof(vis));

    while(!pq.empty()){
        b = pq.top().f;
        from = pq.top().s;

        pq.pop();
        
        if(vis[from]) {
            continue;
        }
        vis[from]=1;
        for(pi i : g[from]){
            int to = i.f;
            int w= i.s;
      
            if(dis[to][0]> b+w){
                bool flag = false;
                if(dis[to][0]!=INF) flag = true;
                dis[to][1] = dis[to][0];
                dis[to][0] = dis[from][1]+w;
                if(flag)pq.push({dis[to][1], to});
            }
            else if(dis[to][1]>b+w){
                dis[to][1]=dis[from][1]+w;
                pq.push({dis[to][1], to});
            }
           
        }
       
    }

   
     return dis[0][1]; 

}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2896 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2904 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2896 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2904 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 3 ms 3160 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 4 ms 3420 KB Output is correct
13 Correct 3 ms 3420 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2896 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2904 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 3 ms 3160 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 4 ms 3420 KB Output is correct
13 Correct 3 ms 3420 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 256 ms 67016 KB Output is correct
17 Correct 58 ms 14672 KB Output is correct
18 Correct 55 ms 16976 KB Output is correct
19 Correct 305 ms 73312 KB Output is correct
20 Correct 184 ms 55072 KB Output is correct
21 Correct 23 ms 8536 KB Output is correct
22 Correct 178 ms 50004 KB Output is correct