Submission #521038

#	Time	Username	Problem	Language	Result	Execution time	Memory
521038		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1083 ms	2016 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][5], wazne[LIM], n, m;
void dijkstra(int v, int odw, int f, int z) {
	rep(i, n) odl[i][f]=odl[i][4]=INF;
	priority_queue<pair<int,pair<int,int>>>q;
	q.push({0, {v, -1}});
	odl[v][4]=0;
	while(!q.empty()) {
		int o=-q.top().st, p=q.top().nd.st, lst=q.top().nd.nd; q.pop();
		if(odl[p][f]<=o) continue;
		odl[p][f]=o;
		if(z) wazne[lst]=1;
		for(auto i : V[p]) {
			if(!odw) {
				if(kraw[i].st.st==p && o+kraw[i].nd.st<odl[kraw[i].st.nd][f]) {
					if(o+kraw[i].nd.st<odl[kraw[i].st.nd][4]) {
						odl[kraw[i].st.nd][4]=o+kraw[i].nd.st;
						q.push({-o-kraw[i].nd.st, {kraw[i].st.nd, i}});
					}
				}
			} else {
				if(kraw[i].st.nd==p && o+kraw[i].nd.st<odl[kraw[i].st.st][f]) {
					if(o+kraw[i].nd.st<odl[kraw[i].st.st][4]) {
						odl[kraw[i].st.st][4]=o+kraw[i].nd.st;
						q.push({-o-kraw[i].nd.st, {kraw[i].st.st, i}});
					}
				}
			}
		}
	}
}
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