Submission #206716

#	Time	Username	Problem	Language	Result	Execution time	Memory
206716		Saboon	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1090 ms	1912 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);
	for (int i = 0; i < m; i++){
		swap(a[i], b[i]);
		ans[i] += shpa(src, snk);
		swap(a[i], b[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;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void solve(int, int)':
ho_t4.cpp:74:6: warning: unused variable 'now' [-Wunused-variable]
  int now = shpa(src, snk);
      ^~~

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