oj.uz

Submission #314695

# Submission time Handle Problem Language Result Execution time Memory
314695 2020-10-20T22:28:35 Z aZvezda Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 6592 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 2e2 + 10, MAX_W = 1e5 + 10;
vector<pair<pair<ll, ll>, pair<ll, ll> > > edges;
bool off[MAX_W];
vector<pair<pair<ll, ll>, ll> > g[MAX_N];
ll dist[4][MAX_N];
ll n, m;

void dij(ll ind, ll start) {
	for(ll i = 0; i < MAX_N; i ++) {
		dist[ind][i] = mod;
	}
	priority_queue<pair<ll, ll> > pq;
	pq.push({0, start});
	dist[ind][start] = 0;
	while(!pq.empty()) {
		auto curr = pq.top(); pq.pop();
		curr.first *= -1;
		for(auto it : g[curr.second]) {
			if(off[it.second]) {continue;}
			ll nxt = it.first.first;
			if(dist[ind][nxt] > curr.first + it.first.second) {
				dist[ind][nxt] = curr.first + it.first.second;
				pq.push({-dist[ind][nxt], nxt});
			}	
		}
	}
	return;
	cout << "Started from " << start << endl;
	for(ll i = 1; i <= n; i ++) {
		cout << dist[ind][i] << " ";
	}
	cout << endl;
} 

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	edges.resize(m);
	for(ll i = 0; i < m; i ++) {
		cin >> edges[i];
		off[2 * i] = false;
		off[2 * i + 1] = true;
		g[edges[i].first.first].push_back({{edges[i].first.second, edges[i].second.first}, 2 * i}); 
		g[edges[i].first.second].push_back({{edges[i].first.first, edges[i].second.first}, 2 * i + 1}); 
	}
	dij(0, 1);
	dij(1, n);
	ll ret = dist[0][n] + dist[1][1];
	for(ll i = 0; i < m; i ++) {
		off[2 * i] = true;
		off[2 * i + 1] = false;
		dij(2, 1);
		dij(3, n);
		chkmin(ret, edges[i].second.second + dist[2][n] + dist[3][1]);
		off[2 * i] = false;
		off[2 * i + 1] = true;
	}
	cout << ret << endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 512 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 6592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 528 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 512 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -