Submission #545042

#	Time	Username	Problem	Language	Result	Execution time	Memory
545042		Asymmetry	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	105 ms	4308 KiB

ho_t4

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct edge {
	int c, d;
};

const int N = 210;
const int M = 50100;
int n, m;
vector<edge> kr[N][N];
long long odp;
int odw[N];
long long v[2][N][N];
long long odl[2][2][N][N]; // czy obrócone krawędzie | z 1 / N | z wyłączeniem kogo | do kogo

void wylicz(long long odl[N], long long v[N][N], int src, int bez) {
	for (int i = 1; i <= n; ++i) {
		odl[i] = 1e18;
		odw[i] = 0;
	}
	odw[bez] = 1;
	odl[src] = 0;
	for (int i = 1; i <= n; ++i) {
		int x = 0;
		long long od = 1e18;
		for (int j = 1; j <= n; ++j) {
			if (odw[j]) {
				continue;
			}
			if (od > odl[j]) {
				x = j;
				od = odl[j];
			}
		}
		if (!x) {
			return;
		}
		for (int j = 1; j <= n; ++j) {
			odl[j] = min(odl[j], odl[x] + v[x][j]);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			v[0][i][j] = v[1][i][j] = 1e18;
		}
	}
	for (int i = 1; i <= m; ++i) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		kr[a][b].push_back({c, d});
		v[0][a][b] = min(v[0][a][b], (long long)c);
		v[1][b][a] = min(v[1][b][a], (long long)c);
	}
	
	for (int i = 1; i <= n + 1; ++i) {
		wylicz(odl[0][0][i], v[0], 1, i);
		wylicz(odl[1][0][i], v[1], 1, i);
		wylicz(odl[0][1][i], v[0], n, i);
		wylicz(odl[1][1][i], v[1], n, i);
	}
	
	odp = odl[0][0][n + 1][n] + odl[0][1][n + 1][1]; // bez obracania krawędzi
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			// obracamy krawędź z i do j
			vector<long long> cost;
			cost.push_back(1e18);
			for (auto k : kr[i][j]) {
				cost.push_back(min(cost.back(), (long long)k.c));
			}
			long long suf = 1e18;
			reverse(kr[i][j].begin(), kr[i][j].end());
			for (auto k : kr[i][j]) {
				cost.pop_back();
				
				long long c1n1 = odl[0][0][j][i] + min(cost.back(), suf) + odl[1][1][i][j];
				long long c1n2 = 1e18;
				long long c1n3 = odl[0][0][i][j] + k.c + odl[1][1][j][i];
				for (int g = 1; g <= n; ++g) {
					c1n2 = min(c1n2, odl[0][0][j][g] + odl[1][1][i][g]);
				}
				
				long long cn11 = odl[0][1][j][i] + min(cost.back(), suf) + odl[1][0][i][j];
				long long cn12 = 1e18;
				long long cn13 = odl[0][1][i][j] + k.c + odl[1][0][j][i];
				for (int g = 1; g <= n; ++g) {
					cn12 = min(cn12, odl[0][1][i][g] + odl[1][0][j][g]);
				}
				
				odp = min(odp, c1n1 + cn11);
				odp = min(odp, c1n1 + cn12);
				odp = min(odp, c1n1 + cn13 + k.d);
				
				odp = min(odp, c1n2 + cn11);
				odp = min(odp, c1n2 + cn12);
				odp = min(odp, c1n2 + cn13 + k.d);
				
				odp = min(odp, c1n3 + cn11 + k.d);
				odp = min(odp, c1n3 + cn12 + k.d);
				odp = min(odp, c1n3 + cn13 + k.d);
				
				suf = min(suf, (long long)k.c);
			}
		}
	}
	
	if (odp > 1e14) {
		printf("-1\n");
		return 0;
	}
	printf("%lld\n", odp);
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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