Submission #923374

#	Time	Username	Problem	Language	Result	Execution time	Memory
923374		vjudge1	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	745 ms	6104 KiB

ho_t4

// put it before the include
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
#define int long long
const int inf = 1e18 + 7;
void solve(){
	int n,m;
	cin >> n >> m;
	vector < vector < pair < int , int > > > graph(n+1) , igraph(n+1);
	array < int , 4 > edge[m];
	bool is_in_path[m];
	memset(is_in_path , 0 , sizeof(is_in_path));
	for(int i = 0;i<m;i++){
		cin >> edge[i][0] >> edge[i][1] >> edge[i][2] >> edge[i][3];
		graph[edge[i][0]].push_back({edge[i][1] , i});
		igraph[edge[i][1]].push_back({edge[i][0] , i});
	}
	auto eval = [&](int st , vector < vector < pair < int , int > > > G , int forbidden){
		vector < int > vis(n+1 , inf);
		vector < pair < int , int > >  pq(n+1 , {inf , inf});
		pq[st] = {0,-1};
		// cout << "forbidden : " << forbidden << endl;
		while(true){
			int tmp = -1;
			pair < int , int > val = {inf,inf};
			for(int i = 1;i<=n;i++){
				if(vis[i] == inf and val > pq[i]){
					tmp = i;
					val = pq[i];
				}
			}
			if(tmp == -1 or val.first == inf)break;
			// cout << "bfs : " << tmp << " " << val.first << " " << val.second << endl;
			// cout << "G : ";for(int i = 0;i<sz(G[tmp]);i++)cout << G[tmp][i].first << " ";cout << endl;
			vis[tmp] = val.first;
			if(val.second != -1 and forbidden == -1){
				is_in_path[val.second] = 1;
			}
			for(int i = 0;i<sz(G[tmp]);i++){
				if(G[tmp][i].second != forbidden){
					array < int , 4 > ed = edge[G[tmp][i].second];
					pq[G[tmp][i].first] = min(pq[G[tmp][i].first] , {val.first + ed[2] , G[tmp][i].second});
				}
			}
		}
		// cout << st << " : ";for(int i = 1;i<=n;i++)cout << vis[i] << " ";cout << endl;
		return vis;
	};
	vector < int > from1 = eval(1 , graph , -1);
	vector < int > fromn = eval(n , graph , -1);
	vector < int > to1 = eval(1 , igraph , -1);
	vector < int > ton = eval(n , igraph , -1);
	int ans = from1[n] + fromn[1];
	int sayac = 0;
	for(int i = 0;i<m;i++){
		// cout << "edge : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
		int r1 , r2;
		if(is_in_path[i]){
			// cout << "sayac : " << sayac << " " << i << endl;
			sayac++;
			// cout << "special : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
			vector < int > tfrom1 = eval(1 , graph , i);
			// cout << "tfrom1 : ";for(int i = 1;i<=n;i++)cout << tfrom1[i] << " ";cout << endl;
			vector < int > tfromn = eval(n , graph , i);
			// cout << "tfromn : ";for(int i = 1;i<=n;i++)cout << tfromn[i] << " ";cout << endl;
			vector < int > tto1 = eval(1 , igraph , i);
			// cout << "tto1 : ";for(int i = 1;i<=n;i++)cout << tto1[i] << " ";cout << endl;
			vector < int > tton = eval(n , igraph , i);
			// cout << "tton : ";for(int i = 1;i<=n;i++)cout << tton[i] << " ";cout << endl;
			r1 = min(tfrom1[n] , tfrom1[edge[i][1]] + edge[i][2] + tton[edge[i][0]]);//gidis
			r2 = min(tfromn[1] , tfromn[edge[i][1]] + edge[i][2] + tto1[edge[i][0]]);//donus
			// cout << "r : " << r1 << " " << r2 << endl;
		}
		else{
			// cout << "ordinary : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
			r1 = min(from1[n] , from1[edge[i][1]] + edge[i][2] + ton[edge[i][0]]);//gidis
			r2 = min(fromn[1] , fromn[edge[i][1]] + edge[i][2] + to1[edge[i][0]]);//donus
			// cout << "r : " << r1 << " " << r2 << endl;
			// cout << "donus : " << fromn[edge[i][1]] << " + " << edge[i][2] << " + " << to1[edge[i][0]] << endl;
		}
		// cout << "######" << endl;
		ans = min(ans , edge[i][3] + r1 + r2);
	}
	cout << (ans >= inf ? -1 : ans) << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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