Submission #534306

#	Time	Username	Problem	Language	Result	Execution time	Memory
534306		Haruto810198	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	28 ms	1868 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = 1e18;
const int MOD = 1000000007;
const double eps = 1e-12;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

const int MAX = 210;

int n, m;
int dis[MAX][MAX];
int dis2[MAX][MAX];
int res;

void FloydWarshall(){
	FOR(k, 1, n, 1){
		FOR(i, 1, n, 1){
			FOR(j, 1, n, 1){
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}

// 1 -> n, n -> 1
vector<pii> eout, ein;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	FOR(i, 1, n, 1){
		FOR(j, 1, n, 1){
			dis[i][j] = dis2[i][j] = LNF;
		}
	}

	FOR(i, 1, m, 1){
		int u, v, c, d;
		cin>>u>>v>>c>>d;
		dis[u][v] = min(dis[u][v], c);
		dis2[v][u] = min(dis2[v][u], c+d);
		
		if(u == 1 and v == n) eout.eb(c, c+d);
		if(u == n and v == 1) ein.eb(c, c+d);
	}
	
	FloydWarshall();
	
	// not inverting an edge
	int res = dis[1][n] + dis[n][1];
	cerr<<"not inverting : "<<res<<endl;

	// len. of cycle >= 3 :
	// 1 ~> u -> n -> 1
	// 1 -> u ~> n -> 1
	// 1 -> u -> n ~> 1
	int owo = LNF;
	FOR(u, 2, n-1, 1){
		res = min({res,
		dis2[1][u] + dis[u][n] + dis[n][1], 
		dis[1][u] + dis2[u][n] + dis[n][1],
		dis[1][u] + dis[u][n] + dis2[n][1],

		dis2[u][1] + dis[n][u] + dis[1][n], 
		dis[u][1] + dis2[n][u] + dis[1][n],
		dis[u][1] + dis[n][u] + dis2[1][n]
		});

		owo = min({owo,
		dis2[1][u] + dis[u][n] + dis[n][1], 
		dis[1][u] + dis2[u][n] + dis[n][1],
		dis[1][u] + dis[u][n] + dis2[n][1],

		dis2[u][1] + dis[n][u] + dis[1][n], 
		dis[u][1] + dis2[n][u] + dis[1][n],
		dis[u][1] + dis[n][u] + dis2[1][n]
		});
	}
	cerr<<"len = 3 : "<<owo<<endl;

	// len. of cycle == 2 : special case
	// 1 -> n -> 1
	res = min(res, dis[1][n] + dis[n][1]);
	owo = dis[1][n] + dis[n][1];

	// 1 -> n ~> 1
	multiset<int> st;
	for(pii e : eout) st.insert(e.F);
	for(pii e : eout){
		st.erase(st.find(e.F));
		if(!st.empty()){
			res = min(res, e.S + *st.begin());
			owo = min(owo, e.S + *st.begin());
		}
		st.insert(e.F);
	}

	// 1 ~> n -> 1
	st.clear();
	for(pii e : ein) st.insert(e.F);
	for(pii e : ein){
		st.erase(st.find(e.F));
		if(!st.empty()){
			res = min(res, e.S + *st.begin());
			owo = min(owo, e.S + *st.begin());
		}
		st.insert(e.F);
	}

	cerr<<"len = 2 : "<<owo<<endl;
	
	if(res < LNF) cout<<res<<'\n';
	else cout<<-1<<'\n';

	return 0;

}

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