Submission #243959

#	Time	Username	Problem	Language	Result	Execution time	Memory
243959		pit4h	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1097 ms	2176 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;

const int N = 201, M = 5e4+1;
const long long INF = 1e12+1;
int n, m, u[M], v[M];
long long c[M], d[M];
long long G[N][N], W[N][N];
pair<long long, int> shortest[N][2];

long long solve(int p, int q) {

	long long ans = INF;

	for(int i=0; i<m; ++i) {

		long long path[2] = {0, 0};
		path[1] = G[q][v[i]] + c[i] + d[i] + G[u[i]][p];
		path[0] = INF;

		if(G[p][u[i]] + W[u[i]][v[i]] + G[v[i]][q] > G[p][q]) path[0] = G[p][q];

		else for(int j=1; j<=n; ++j) {
			if(G[p][j] > G[p][u[i]]) continue;
			// G[p][j] <= G[p][u[i]]
			if(j != u[i] || q != v[i]) {
				path[0] = min(path[0], G[p][j] + W[j][q]);
			}
			for(int k=1; k<=n; ++k) { if(k==j) continue;
				if(G[k][q] > G[u[i]][q] || (j==u[i] && k==v[i]) || k==u[i]) continue;
				// G[k][q] <= G[u[i]][q]
				path[0] = min(path[0], G[p][j] + W[j][k] + G[k][q]);	
			}
		}	

		ans = min(ans, path[0] + path[1]);
	}
	return ans;
}

int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;

	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			G[i][j] = INF;
			W[i][j] = INF;
		}
		G[i][i] = 0;
	}

	for(int i=0; i<m; ++i) {
		cin>>u[i]>>v[i]>>c[i]>>d[i];
		G[u[i]][v[i]] = min(G[u[i]][v[i]], c[i]);
		W[u[i]][v[i]] = min(W[u[i]][v[i]], c[i]);
	}

	for(int k=1; k<=n; ++k) {
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);	
			}
		}
	}

	for(int i=1; i<=n; ++i) {
		shortest[i][0] = shortest[i][1] = make_pair(INF, 0);
		for(int j=1; j<=n; ++j) {
			if(i==j) continue;
			int path = G[1][i] + W[i][j] + G[j][n];
			if(path <= shortest[i][0].first) {
				shortest[i][1] = shortest[i][0];
				shortest[i][0] = {path, j};
			}
			else if(path < shortest[i][1].first) {
				shortest[i][1] = {path, j};
			}
		}
	}

	
	long long ans = min({G[1][n]+G[n][1], solve(1, n), solve(n, 1)});
	if(ans >= INF) cout<<-1;
	else cout<<ans;
}

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