oj.uz

Submission #230089

# Submission time Handle Problem Language Result Execution time Memory
230089 2020-05-08T07:30:28 Z grt Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 2816 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const ll INF = 1e18;
const int nax = 210, mx = 50*1000+10;
int n,m;
vector<pi> V[nax];
pi edge[mx];
int inv[mx], cost[mx];
ll dist[nax];
bool done[nax];

void dijkstra(int x) {
	priority_queue<pair<ll,int> > PQ;
	PQ.push({0,x});
	for(int i = 1; i <= n; ++i) dist[i] = INF;
	dist[x] = 0;
	while(!PQ.empty()) {
		pair<ll,int>tp = PQ.top();
		PQ.pop();
		tp.ST = -tp.ST;
		if(dist[tp.ND] < tp.ST) continue;
		for(auto nbh : V[tp.ND]) {
			if(!done[nbh.ND]) {
				if(dist[nbh.ST] > tp.ST + cost[nbh.ND]) {
					dist[nbh.ST] = tp.ST + cost[nbh.ND];
					PQ.push({-dist[nbh.ST],nbh.ST});
				}
			}
		}
	}
}

int main() {_
	cin >> n >> m;
	for(int a,b,i = 1; i <= m; ++i) {
		cin >> a >> b >> cost[i] >> inv[i];
		edge[i] = {a,b};
		V[a].PB({b,i});
	}
	ll ans = INF;
	for(int i = 1; i <= m; ++i) {
		ll c = inv[i];
		int a = edge[i].ST, b = edge[i].ND;
		V[b].PB({a,m+1});
		cost[m+1] = cost[i];
		done[i] = 1;
		dijkstra(1);
		c += dist[n];
		//cout << inv[i] << " ";
		//cout << dist[n] << " ";
		dijkstra(n);
		c += dist[1];
		//cout << dist[1] << "\n"; 
		done[i] = 0;
		ans = min(ans,c);
		V[b].pop_back();
	}
	if(ans == INF) cout << "-1";
	else cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -