제출 #996458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996458		yellowtoad	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	395 ms	99664 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;

long long dist[100010][2], vis[100010][2];
vector<pair<int,long long>> edge[100010];
priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>> pq;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
  for (int i = 0; i < m; i++) {
    edge[R[i][0]].push_back({R[i][1],L[i]});
    edge[R[i][1]].push_back({R[i][0],L[i]});
  }
  for (int i = 0; i < n; i++) dist[i][0] = dist[i][1] = 1e18;
  for (int i = 0; i < k; i++) {
    dist[P[i]][0] = dist[P[i]][1] = 0;
    pq.push({0,{P[i],0}});
    pq.push({0,{P[i],1}});
  }
  while (pq.size()) {
    int u = pq.top().s.f, v = pq.top().s.s;
    pq.pop();
    if (vis[u][v]) continue;
    vis[u][v] = 1;
    if (!v) continue;
    for (int i = 0; i < edge[u].size(); i++) {
      if (dist[edge[u][i].f][0] > dist[u][1]+edge[u][i].s) {
        dist[edge[u][i].f][1] = dist[edge[u][i].f][0];
        dist[edge[u][i].f][0] = dist[u][1]+edge[u][i].s;
        pq.push({dist[edge[u][i].f][0],{edge[u][i].f,0}});
        pq.push({dist[edge[u][i].f][1],{edge[u][i].f,1}});
      } else if (dist[edge[u][i].f][1] > dist[u][1]+edge[u][i].s) {
        dist[edge[u][i].f][1] = dist[u][1]+edge[u][i].s;
        pq.push({dist[edge[u][i].f][1],{edge[u][i].f,1}});
      }
    }
  }
  return dist[0][1];
}

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

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < edge[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

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