This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <bits/stdc++.h>
#define debug(args...) //fprintf(stderr, args)
#define mk make_pair
using namespace std;
const int maxn = 2e5, INF = 1e9;
int dist[maxn],distMin[maxn],marcExit[maxn],contExit[maxn],resp,n;
vector<int> grafo[maxn];
vector<int> peso[maxn];
vector<int> casos[maxn];
set<pair<int, int> > fora;
void dijkstra()
{
debug("dijkstra\n");
debug("set foi!!\n");
debug("criei os set ai\n");
for(int x = 0; x < n; x++) fora.insert( mk(dist[x], x));
debug("inicializei dnv\n");
while(!fora.empty())
{
int cur = fora.begin()->second;
debug(" %d:\n",cur);
fora.erase(fora.begin());
for(int x = 0; x < grafo[cur].size(); x++)
{
int viz = grafo[cur][x];
debug(" %d\n",viz);
int p = peso[cur][x];
if(dist[cur] + p < distMin[viz])
{
fora.erase( mk(dist[viz], viz));
dist[viz] = distMin[viz];
distMin[viz] = dist[cur] + p;
fora.insert( mk(dist[viz], viz));
continue;
}
if(dist[cur] + p < dist[viz])
{
fora.erase( mk(dist[viz], viz));
dist[viz] = dist[cur] + p;
fora.insert( mk(dist[viz], viz));
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
debug("comeco\n");
n = N;
for(int x = 0; x < K; x++) marcExit[P[x]] = 1;
for(int x = 0; x < M; x++)
{
int i = R[x][0];
int j = R[x][1];
int p = L[x];
grafo[i].push_back(j);
grafo[j].push_back(i);
peso[i].push_back(p);
peso[j].push_back(p);
if(marcExit[i] && marcExit[j]) continue;
if(marcExit[i]) contExit[j]++;
if(marcExit[j]) contExit[i]++;
}
debug("criou o grafo\n");
for(int x = 0; x < N; x++)
{
if(marcExit[x])
{
distMin[x] = 0;
dist[x] = 0;
}
else
{
distMin[x] = INF;
dist[x] = INF;
}
if(contExit[x] >= 2)
{
int Min = INF;
int Max = INF;
for(int y = 0; y < grafo[x].size(); y++)
{
int viz = grafo[x][y];
int p = peso[x][y];
if(dist[viz] + p < Min)
{
Max = Min;
Min = dist[viz] + p;
continue;
}
if(dist[viz] + p < Max) Max = dist[viz] + p;
}
dist[x] = Max;
}
}
debug("terminei a entrada\n");
dijkstra();
debug("foi o dijkstra\n");
int resp = dist[0];
debug("resp = %d\n",resp);
return resp;
}
Compilation message (stderr)
crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x = 0; x < grafo[cur].size(); x++)
~~^~~~~~~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int y = 0; y < grafo[x].size(); y++)
~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |