oj.uz

Submission #506193

# Submission time Handle Problem Language Result Execution time Memory
506193 2022-01-11T20:20:30 Z thomas_li Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 2788 KB 
#include <bits/stdc++.h>
using namespace std;
const int MM = 205,MV = 5e4+5;
int n,m; vector<array<int,2>> adj[MM];
array<int,4> el[MV];
int64_t dist[MM];
void go(int st, int en){
	memset(dist,0x3f,sizeof dist);
	dist[st] = 0;
	priority_queue<pair<int64_t,int>,vector<pair<int64_t,int>>,greater<pair<int64_t,int>>> q;
	q.push({0,st});
	while(q.size()){
		auto[d,u] = q.top(); q.pop();
		if(d > dist[u]) continue;
		for(auto[v,w] : adj[u]) if(dist[v] > dist[u] + w){
			dist[v] = dist[u]+w;
			q.push({dist[v],v});
		}
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		el[i] = {a,b,c,d};
	}
	int64_t ans = 1e18;
	for(int i = 1; i <= m; i++){
		swap(el[i][0],el[i][1]);
		for(int j = 1; j <= n; j++){
			adj[j].clear();	
		}
		for(int j = 1; j <= m; j++){
			auto[a,b,c,d] = el[j];
			adj[a].push_back({b,c});
		}
		go(1,n);	
		int64_t cur = dist[n];
		go(n,1);
		cur += dist[1];
		cur += el[i][3];
		ans = min(ans,cur);
		swap(el[i][0],el[i][1]);
	}
	{
		for(int j = 1; j <= n; j++){
			adj[j].clear();	
		}
		for(int j = 1; j <= m; j++){
			auto[a,b,c,d] = el[j];
			adj[a].push_back({b,c});
		}
		go(1,n);	
		int64_t cur = dist[n];
		go(n,1);
		cur += dist[1];
		ans = min(ans,cur);
	}
	cout << (ans > 2e9 ? -1 : ans) << "\n";
}
// O(M*(M log M)) - fix edge and run dijkstra
// do N*M dijkstra dp[node u][changed edge id]

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 360 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 50 ms 368 KB Output is correct
4 Correct 54 ms 392 KB Output is correct
5 Correct 22 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 72 ms 332 KB Output is correct
11 Correct 68 ms 368 KB Output is correct
12 Correct 85 ms 336 KB Output is correct
13 Correct 30 ms 388 KB Output is correct
14 Correct 42 ms 380 KB Output is correct
15 Correct 33 ms 376 KB Output is correct
16 Correct 34 ms 332 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Execution timed out 1069 ms 2072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 360 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 50 ms 368 KB Output is correct
4 Correct 54 ms 392 KB Output is correct
5 Correct 22 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 11 ms 332 KB Output is correct
10 Correct 72 ms 332 KB Output is correct
11 Correct 68 ms 368 KB Output is correct
12 Correct 85 ms 336 KB Output is correct
13 Correct 30 ms 388 KB Output is correct
14 Correct 42 ms 380 KB Output is correct
15 Correct 33 ms 376 KB Output is correct
16 Correct 34 ms 332 KB Output is correct
17 Execution timed out 1051 ms 2788 KB Time limit exceeded
18 Halted 0 ms 0 KB -