제출 #522344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522344		new_acc	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	1555 ms	129248 KiB

crocodile

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
vector<pair<int,ll> > graf[N];
int vis[N];
ll travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
	rep(i,m) graf[r[i][0]].push_back({r[i][1],l[i]}),graf[r[i][1]].push_back({r[i][0],l[i]});
	multiset<pair<ll,int> >s;
	rep(i,k) s.insert({0,p[i]}),vis[p[i]]=1;
	while(!s.empty()){
		auto it=s.begin();
		s.erase(it);
		int v=(*it).se;
		ll c=(*it).fi;
		if(vis[v]==0){vis[v]=1;continue;}
		if(vis[v]>1) continue;
		vis[v]++;
		if(v==0) return c;
		for(auto u:graf[v]){
			ll c2=c+u.se;
			if(vis[u.fi]<2) s.insert({c2,u.fi});
		}
	}
	return 0;
}
/*int main(){
	int n,m,k;
	cin>>n>>m>>k;
	int r[m][2],l[m],p[k];
	rep(i,m) cin>>r[i][0]>>r[i][1]>>l[i];

	rep(i,k) cin>>p[i];
	cout<<travel_plan(n,m,r,l,k,p)<<"\n";
}*/

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