Submission #506191

#	Time	Username	Problem	Language	Result	Execution time	Memory
506191		thomas_li	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1 ms	560 KiB

ho_t4

// brute
#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[MM];
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: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63