Submission #138718

#	Time	Username	Problem	Language	Result	Execution time	Memory
138718		MrBrionix	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1004 ms	65056 KiB

crocodile

//#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
/*
#define MAX_N 100005
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  //my_assert(1==scanf("%d",&solution));
}
*/

vector<int> grafo[100005],peso[100005];
int sol[100005][2],n,m,tmp;
priority_queue<pair<int,int> > pq;
bool ok[100005];
/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1
3
4


7 6 4
0 1 5
0 2 3
1 3 3
1 4 5
2 5 2
2 6 6
3 4 5 6
*/

void dfs(int nodo){
    
    for(int i=0;i<grafo[nodo].size();i++){
        
        if(sol[grafo[nodo][i]][0]==-1 || sol[grafo[nodo][i]][0]>(sol[nodo][1]+peso[nodo][i])){
            sol[grafo[nodo][i]][1]=sol[grafo[nodo][i]][0];
            sol[grafo[nodo][i]][0]=sol[nodo][1]+peso[nodo][i];
            if(sol[grafo[nodo][i]][1]!=-1){
                pq.push({-sol[grafo[nodo][i]][1],grafo[nodo][i]});
                ok[grafo[nodo][i]]=true;
            }
        }
        else{
            if(sol[grafo[nodo][i]][1]==-1 || sol[grafo[nodo][i]][1]>(sol[nodo][1]+peso[nodo][i])){
                sol[grafo[nodo][i]][1]=sol[nodo][1]+peso[nodo][i];
                pq.push({-sol[grafo[nodo][i]][1],grafo[nodo][i]});
                ok[grafo[nodo][i]]=true;
            }
        }
        
    }
    ok[nodo]=false;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    
    for(int i=0;i<M;i++){
        grafo[R[i][0]].push_back(R[i][1]);
        grafo[R[i][1]].push_back(R[i][0]);
        peso[R[i][0]].push_back(L[i]);
        peso[R[i][1]].push_back(L[i]);
    }
    
    for(int i=0;i<N;i++)sol[i][0]=sol[i][1]=-1;
    
    for(int i=0;i<K;i++){
        sol[P[i]][0]=sol[P[i]][1]=0;
        ok[P[i]]=true;
        pq.push({0,P[i]});
    }
    
    while(pq.size()>0){
        tmp=pq.top().second;
        pq.pop();
        
        if(ok[tmp]){
            dfs(tmp);
            ok[tmp]=false;
        }
        //if(tmp==0)break;
    }
    
    //for(int i=0;i<N;i++)cout<<sol[i][0]<<" "<<sol[i][1]<<endl;
    
    return sol[0][1];
}



/*

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  cout<<ans<<endl;
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

Compilation message (stderr)

crocodile.cpp: In function 'void dfs(int)':
crocodile.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~

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