Submission #1268600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268600		nhnguyen14	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	222 ms	327680 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 200;
const int M  = (int) 5e4;
const LL inf = (LL)1e18;
	int x[M + 2] , y[M + 2] , c[M + 2] , d[M + 2];
	int n , m;

	vector<int> ke[N + 2][2];
		void add_canh(int u , int v , int id , int t){
			ke[u][t].push_back(id);
			return;
		}
		
	LL dist[2][N + 2][M + 2][2] = {};
	
	struct Node{
		LL cost;
		int u , id_canh;
		bool change_canh;
		bool operator < (const Node&other) const{
			return cost > other.cost;
		}
	};
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> m;
		for(int i = 1; i <= m; ++i) {
			cin >> x[i] >> y[i] >> c[i] >> d[i];
			add_canh(x[i] , y[i] , i , 0);
			add_canh(y[i] , x[i] , i , 1);
		}
		
		memset(dist[0] , 0x3f , sizeof dist[0]);
		memset(dist[1] , 0x3f , sizeof dist[1]);
		
		
		priority_queue<Node> pq;
		dist[0][1][0][0] = 0;
		pq.push({dist[0][1][0][0] , 1 , 0 , 0});
		while (pq.size()){
			int u = pq.top().u , _id = pq.top().id_canh ;
			bool tt = pq.top().change_canh;
			LL cost = pq.top().cost;
			pq.pop();
			if (cost != dist[0][u][_id][tt]) continue;
				if (_id == 0 && tt == 0){
					for(int id : ke[u][1]){
						int v = u ^ x[id] ^ y[id];
						if (minimize(dist[0][v][id][0] , cost + c[id] + d[id])) pq.push({dist[0][v][id][0] , v , id , 0});
					}
					for(int id : ke[u][0]){
						int v = u ^ x[id] ^ y[id];
						if (minimize(dist[0][u][id][1] , cost + d[id])) pq.push({dist[0][u][id][1] , u , id , 1});
					}
				}
				
			for(int id : ke[u][0]){
				if (id == _id) continue;
				int v = x[id] ^ y[id] ^ u;
				
				if (minimize(dist[0][v][_id][tt] , cost + c[id])) pq.push({dist[0][v][_id][tt] , v , _id , tt});
			}
		}
				
		for(int i = 0; i <= m; ++i){
			dist[1][n][i][0] = dist[0][n][i][0];
			dist[1][n][i][1] = dist[0][n][i][1];
			pq.push({dist[1][n][i][0] , n , i , 0});
			pq.push({dist[1][n][i][1] , n , i , 1});
		}
		
		while (pq.size()){
			int u = pq.top().u , _id = pq.top().id_canh;
			bool tt = pq.top().change_canh;
			LL cost = pq.top().cost;
			pq.pop();
			if (cost != dist[1][u][_id][tt]) continue;
//			cout << u << ' ' << _id << ' ' << tt <<  " COST : " << cost << '\n';
			if (tt == 1){
				for(int id : ke[u][1]){
					if (id != _id) continue;
					int v = u ^ x[id] ^ y[id];
					if (minimize(dist[1][v][_id][tt] , cost + c[id])) pq.push({dist[1][v][_id][tt] , v , _id , tt});
				}
			}
			for(int id : ke[u][0]){
				if (id == _id) continue;
				int v = u ^ x[id] ^ y[id];
				if (minimize(dist[1][v][_id][tt] , cost + c[id])) pq.push({dist[1][v][_id][tt] , v , _id , tt});
			}
		}
		
		LL ans = inf;
		for(int i = 0; i <= m; ++i) {
			minimize(ans , dist[1][1][i][0]);
			minimize(ans , dist[1][1][i][1]);
		}
		if (ans == inf) ans = -1;
		cout << ans;
		
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:57:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:58:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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