제출 #444761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444761		deuslovelt	Olympic Bus (JOI20_ho_t4)	C++17	21 / 100	39 ms	3620 KiB

ho_t4

//================code===================//

//#define TLE

#ifdef TLE
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>
#include <random>
#include <chrono>
//#include <stdint.h>

#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long
#define ld long double
#define fa(i,a,b) for(LL i=(a);i<(LL)(b);++i)
#define fd(i,a,b) for(LL i=(a);i>(LL)(b);--i)
#define setp tuple<LL,LL,LL>
#define setl pair<LL,LL>

#define micro 0.000000001

using namespace std;

ld PI = acos(-1);

LL gcd(LL a, LL b)
{
	if (!(a && b)) return max(a, b);
	return a % b ? gcd(b, a % b) : b;
}

#ifdef OHSOLUTION
#define ce(t) cerr<<t
#define AT cerr << "\n=================ANS=================\n"
#define AE cerr << "\n=====================================\n"
#define DB(a) cerr << __LINE__ << ": " << #a << " = " << (a) << endl;
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#define LLL LL
#else
#define AT
#define AE
#define ce(t)
#define LLL __int128
#endif

pair <int, int> vu[9] = { {0,1},{1,0},{0,-1} ,{-1,0},{-1,0},{-1,-1}, {0,-1} , {1,-1},{-1,-1} }; //RDLU EWSN
mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());


template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl& a, setl& b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl& a, setl& b) { return a.second > b.second; } };

const int max_v = 2e2 + 7;
const int max_k = 2e2 + 7;
const int bsz = (1ll << 22) + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const LL mod = 1e9 + 7; //998244353;
template<typename T, typename U> void MOD(T& a, U b) { a += b; if (a > mod) a -= mod; };

LL dist[max_v][max_v];
vector<int> adj[max_v];

int main()
{
#ifdef OHSOLUTION
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; ci(n >> m);

	struct edge
	{
		LL u, v, c, d;
	};

	memset(dist, 0x3f, sizeof(dist));
	vector<edge> ve(m);
	int cd = 0;
	fa(i, 0, n) dist[i][i] = 0;
	for (auto& x : ve) ci(x.u >> x.v >> x.c >> x.d), --x.u, --x.v,dist[x.u][x.v]= x.c,adj[x.u].push_back(cd++);
	fa(k, 0, n) fa(i, 0, n) fa(j, 0, n) ckmin(dist[i][j], dist[i][k] + dist[k][j]);
	

	auto dijk = [&](int s,int e,int id)
	{
		vector<LL> dist(n, LNF);
		priority_queue<setl, vector<setl>, lcmp> pq;
		dist[s] = 0;
		pq.push({ s,0 });

		while (pq.size())
		{
			auto [u, c] = pq.top(); pq.pop();

			if (dist[u] ^ c) continue;

			if (ve[id].v == u)
			{
				if (dist[ve[id].u] > dist[u] + ve[id].c)
				{
					dist[ve[id].u] = dist[u] + ve[id].c;
					pq.push({ ve[id].u,dist[ve[id].u] });
				}
			}

			for (auto& x : adj[u]) if(x != id)
			{
				if (dist[ve[x].v] > dist[u] + ve[x].c)
				{
					dist[ve[x].v] = dist[u] + ve[x].c;
					pq.push({ ve[x].v, dist[ve[x].v] });
				}

			}
		}

		return dist[e];
	};

	LL ans = dist[0][n - 1] + dist[n - 1][0];
	int c = 0;
	for (auto& x : ve)
	{
		LL l = min(dist[0][n - 1], dist[0][x.v] + dist[x.u][n - 1] + x.c);
		LL r = min(dist[n - 1][0], dist[n - 1][x.v] + dist[x.u][0] + x.c);
		
		if (l + r + x.d < ans)
		{
			LL rl = dijk(0,n-1,c);
			LL rr = dijk(n-1,0,c);

			ckmin(ans, rl + rr + x.d);
		}

		++c;
	}
	
	ans>=LNF ? co(-1): co(ans);

	return 0;
}

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