제출 #1150494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150494		zhasyn	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	396 ms	68852 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;

vector <pll> q[N];
ll fr[N], last[N], cnt[N];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
  for(int i = 0; i < m; i++){
	q[r[i][0]].pb({r[i][1], l[i]});
	q[r[i][1]].pb({r[i][0], l[i]});
  }
  for(ll i = 0; i < n; i++){
  	last[i] = fr[i] = LLONG_MAX;
  }
  set <pll> st;
  for(int i = 0; i < k; i++){
  	fr[p[i]] = last[p[i]] = 0;
  	st.insert({last[p[i]], p[i]});
  }
  while((ll)st.size() != 0){
  	ll v = st.begin()->S;
  	st.erase(st.begin());
  	for(auto u : q[v]){
  		if(last[v] + u.S <= fr[u.F]){
  			if(fr[u.F] != last[u.F]){
  				st.erase({last[u.F], u.F});
  				last[u.F] = fr[u.F];
  				st.insert({last[u.F], u.F});
  			}
  			fr[u.F] = last[v] + u.S;
  			continue;
  		}
  		if(last[v] + u.S < last[u.F]){
  			st.erase({last[u.F], u.F});
  				last[u.F] = last[v] + u.S;
  				st.insert({last[u.F], u.F});
  		}
  	}
  }
  return last[0];
}


// 
// int main(){
  	// ios::sync_with_stdio(false);
  	// cin.tie(NULL);
//   	
  // return 0;
// }
// 
 

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