| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 13198 | pseudopodia | 악어의 지하 도시 (IOI11_crocodile) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "crocodile.h"
#include <vector>
#include <queue>
#define maxV 100010
#define INF 1000000010
using namespace std;
struct Data{
int val, x;
Data(){}
Data(int x, int val){ this->x = x, this->val = val; }
inline bool operator < (const Data &c) const{
return val > c.val;
}
} top;
struct Node{
int val1, val2;
void init(){ val1=val2=INF; }
bool update(int val)
{
if( val1 > val )
{
val2 = val1, val1 = val;
return true;
}
else if( val2 > val )
{
val2 = val;
return true;
}
return false;
}
}info[maxV];
priority_queue<Data> pq;
vector<int> map[maxV], dist[maxV];
bool visit[maxV];
int travel_plan(int v, int e, int edge[][2], int len[], int exitN, int exit[])
{
for(int i=0;i<v;i++)
{
map[i].clear(), dist[i].clear();
info[i].init(), visit[i] = false;
}
for(int i=0;i<e;i++)
{
map[edge[i][0]].push_back(edge[i][1]);
map[edge[i][1]].push_back(edge[i][0]);
dist[edge[i][0]].push_back(len[i]);
dist[edge[i][1]].push_back(len[i]);
}
while( !pq.empty() ) pq.pop();
for(int i=0;i<exitN;i++) pq.push(Data(exit[i],0));
int x, y, z;
while( !pq.empty() )
{
do{
top = pq.top(), x = top.x;
pq.pop();
}while( visit[top.x] );
if( x == 0 ) return top.val;
visit[x] = true;
for(int j=0;j<map[x].size();j++)
{
y = map[x][j], z = dist[top.x][j];
fflush(stdout);
if( !visit[y] && info[y].update(top.val+z) ) pq.push(Data(y,info[y].val2));
}
}
return -1;
}