제출 #206717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206717		Saboon	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	322 ms	2424 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn = 200 + 10;
const int maxm = 5e4 + 10;
const int inf = 1e9;

int n, m;
int a[maxm], b[maxm], c[maxm], d[maxm];
vector<pair<int,int> > g[maxn];
int dp[maxn], pd[maxn], cn[maxn], pr[maxn];
bool mark[maxn];

int dijkstra(int src, int snk){
	memset(dp, 63, sizeof dp);
	memset(mark, 0, sizeof mark);
	memset(cn, 0, sizeof cn);
	dp[src] = 0;
	for (int i = 0; i < n; i++){
		int v = -1;
		for (int j = 1; j <= n; j++)
			if (!mark[j] and (v == -1 or dp[v] > dp[j]))
				v = j;
		if (v == -1)
			break;
		mark[v] = 1;
		for (auto e : g[v]){
			int idx = e.second;
			int u = e.first, w = c[idx];
			if (dp[u] > dp[v] + w){
				dp[u] = dp[v] + w;
				pr[u] = idx;
				cn[u] = 1;
			}
			else if (dp[u] == dp[v] + w)
				cn[u] ++;
		}
	}
	return dp[snk];
}

int reshpa(int src, int snk){
	for (int i = 0; i < m; i++)
		g[b[i]].push_back({a[i], i});
	for (int i = 1; i <= n; i++)
		pd[i] = dp[i];
	int ret = dijkstra(snk, src);
	for (int i = 1; i <= n; i++){
		swap(dp[i], pd[i]);
		g[i].clear();
	}
	return ret;
}

int shpa(int src, int snk){
	for (int i = 0; i < m; i++)
		g[a[i]].push_back({b[i], i});
	int ret = dijkstra(src, snk);
	for (int i = 1; i <= n; i++)
		g[i].clear();
	return ret;
}

bool visited[maxm];
ll ans[maxm];

void solve(int src, int snk){
	reshpa(src, snk);
	int now = shpa(src, snk);
	memset(visited, 0, sizeof visited);
	if (now <= inf){
		vector<int> sp;
		int tmp = snk;
		while (tmp != src){
			sp.push_back(pr[tmp]);
			tmp = a[pr[tmp]];
		}
		for (auto it : sp){
			swap(a[it], b[it]);
			ans[it] += shpa(src, snk);
			visited[it] = 1;
			swap(a[it], b[it]);
		}
	}
	shpa(src, snk);
	for (int i = 0; i < m; i++){
		if (visited[i])
			continue;
		ll t = dp[b[i]], s = pd[a[i]];
		ans[i] += min((ll)now, s + t + c[i]);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	ll answer = shpa(1, n) + shpa(n, 1);
	solve(1, n);
	solve(n, 1);
	ll t = answer;
	for (int i = 0; i < m; i++){
		answer = min(answer, ans[i] + d[i]);
		t = min(t, ans[i]);
	}
	if (t >= inf)
		return cout << -1 << endl, 0;
	cout << answer << endl;
}

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