제출 #64069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64069		zubec	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	12 ms	7420 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 100100;

vector <pair<int, int> > g[N];

int n, pr[N];

long long d[N];

map<int, int> blockd[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    for (int i = 0; i < M; i++){
        int u = R[i][0]+1, v = R[i][1]+1;
        g[u].push_back({v, L[i]});
        g[v].push_back({u, L[i]});
    }
    set<pair<long long, int> > q;
    for (int i = 1; i <= n; i++)
        d[i] = 1e15;
    for (int i = 0; i < K; i++){
        int v = P[i]+1;
        d[v] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].first, len = g[v][i].second;
            if (d[v] + len < d[to]){
                q.erase({d[to], to});
                d[to] = d[v]+len;
                pr[to] = v;
                q.insert({d[to], to});
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (pr[i] != 0){
            blockd[pr[i]][i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        d[i] = 1e15;
    for (int i = 0; i < K; i++){
        int v = P[i]+1;
        d[v] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].first, len = g[v][i].second;
            if (blockd[v].find(to) != blockd[v].end())
                continue;
            if (d[v] + len < d[to]){
                q.erase({d[to], to});
                d[to] = d[v]+len;
                pr[to] = v;
                q.insert({d[to], to});
            }
        }
    }
    if (d[1] == 1e15)
        d[1] = -1;
    return d[1];

}

/**

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14

*/

컴파일 시 표준 에러 (stderr) 메시지

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~
crocodile.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11