제출 #521065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521065		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	35 ms	3816 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7, INF=2e9+7, K=14;
pair<int,int>xd={INF, INF};
vector<int>V[207], S[207];
pair<pair<int,int>,pair<int,int>>kraw[LIM];
int odl[207][4], wazne[LIM], n, m;
pair<int,int>blok[LIM], mi[LIM];
void dodaj(int v, pair<int,int>x) {
	mi[v]=min(mi[v], x);
	blok[v/K]=min(blok[v/K], x);
}
pair<pair<int,int>,int>znajdz() {
	pair<pair<int,int>,int>p={{INF, INF}, INF};
	rep(i, K+1) p=min(p, {blok[i], i});
	pair<int,int>ans=xd;
	rep(i, K) ans=min(ans, mi[p.nd*K+i]);
	blok[p.nd]=xd;
	rep(i, K) if(mi[p.nd*K+i]==ans) {
		mi[p.nd*K+i]=xd;
		return {ans, p.nd*K+i};
	}
}
void dijkstra(int v, int f, int z) {
	rep(i, n) {
		odl[i][f]=INF;
		blok[i]=mi[i]=xd;
	}
	dodaj(v, {0, -1});
	while(true) {
		pair<pair<int,int>,int>p=znajdz();
		if(p.st==xd) return;
		if(z && p.st.nd!=-1) wazne[p.st.nd]=1;
		odl[p.nd][f]=p.st.st;
		for(auto i : V[p.nd]) if(kraw[i].st.st==p.nd && odl[kraw[i].st.nd][f]==INF) {
			dodaj(kraw[i].st.nd, {odl[p.nd][f]+kraw[i].nd.st, i});
		}
	}
}
void dijkstras(int v, int f, int z) {
	rep(i, n) {
		odl[i][f]=INF;
		blok[i]=mi[i]=xd;
	}
	dodaj(v, {0, -1});
	while(true) {
		pair<pair<int,int>,int>p=znajdz();
		if(p.st==xd) return;
		if(z && p.st.nd!=-1) wazne[p.st.nd]=1;
		odl[p.nd][f]=p.st.st;
		for(auto i : S[p.nd]) if(odl[kraw[i].st.st][f]==INF) {
			dodaj(kraw[i].st.st, {odl[p.nd][f]+kraw[i].nd.st, i});
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, m) {
		cin >> kraw[i].st.st >> kraw[i].st.nd >> kraw[i].nd.st >> kraw[i].nd.nd;
		--kraw[i].st.st; --kraw[i].st.nd;
		V[kraw[i].st.st].pb(i);
		S[kraw[i].st.nd].pb(i);
	}
	dijkstra(0, 0, 1);
	dijkstras(n-1, 1, 1);
	dijkstra(n-1, 2, 1);
	dijkstras(0, 3, 1);
	int ans=INF;
	if(odl[n-1][0]<INF && odl[0][2]<INF) ans=min(ans, odl[n-1][0]+odl[0][2]);
	rep(i, m) if(!wazne[i]) {
		int p1=odl[n-1][0], p2=odl[0][2];
		if(odl[kraw[i].st.nd][0]<INF && odl[kraw[i].st.st][1]<INF) {
			p1=min(p1, odl[kraw[i].st.nd][0]+odl[kraw[i].st.st][1]+kraw[i].nd.st);
		}
		if(odl[kraw[i].st.nd][2]<INF && odl[kraw[i].st.st][3]<INF) {
			p2=min(p2, odl[kraw[i].st.nd][2]+odl[kraw[i].st.st][3]+kraw[i].nd.st);
		}
		if(p1<INF && p2<INF) ans=min(ans, p1+p2+kraw[i].nd.nd);
	}
	rep(i, m) if(wazne[i]) {
		V[kraw[i].st.nd].pb(i);
		swap(kraw[i].st.st, kraw[i].st.nd);
		dijkstra(0, 0, 0);
		dijkstra(n-1, 1, 0);
		if(odl[n-1][0]<INF && odl[0][1]<INF) {
			ans=min(ans, odl[n-1][0]+odl[0][1]+kraw[i].nd.nd);
		}
		swap(kraw[i].st.st, kraw[i].st.nd);
		V[kraw[i].st.nd].pop_back();
	}
	cout << (ans==INF?-1:ans) << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'std::pair<std::pair<int, int>, int> znajdz()':
ho_t4.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63