Submission #521054

#	Time	Username	Problem	Language	Result	Execution time	Memory
521054		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1068 ms	1996 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;
vector<int>V[207];
pair<pair<int,int>,pair<int,int>>kraw[LIM];
int odl[207][4], mi[207], lst[207], wazne[LIM], n, m;
void dijkstra(int v, int odw, int f, int z) {
	rep(i, n) mi[i]=odl[i][f]=lst[i]=INF;
	mi[v]=0;
	rep(i, n) {
		int o=INF, p=-1;
		rep(j, n) if(odl[j][f]==INF && mi[j]<o) {
			o=mi[j];
			p=j;
		}
		if(p==-1) break;
		odl[p][f]=o;
		if(z && lst[p]<INF) wazne[lst[p]]=1;
		for(auto j : V[p]) {
			if(!odw) {
				if(kraw[j].st.st==p && odl[kraw[j].st.nd][f]==INF) {
					if(o+kraw[j].nd.st<mi[kraw[j].st.nd]) {
						mi[kraw[j].st.nd]=o+kraw[j].nd.st;
						lst[kraw[j].st.nd]=j;
					}
				}
			} else {
				if(kraw[j].st.nd==p && odl[kraw[j].st.st][f]==INF) {
					if(o+kraw[j].nd.st<mi[kraw[j].st.st]) {
						mi[kraw[j].st.st]=o+kraw[j].nd.st;
						lst[kraw[j].st.st]=j;
					}
				}
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	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);
		V[kraw[i].st.nd].pb(i);
	}
	rep(i, n) random_shuffle(all(V[i]));
	dijkstra(0, 0, 0, 1);
	dijkstra(n-1, 1, 1, 1);
	dijkstra(n-1, 0, 2, 1);
	dijkstra(0, 1, 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]) {
		swap(kraw[i].st.st, kraw[i].st.nd);
		dijkstra(0, 0, 0, 0);
		dijkstra(n-1, 0, 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);
	}
	cout << (ans==INF?-1:ans) << '\n';
}

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