Submission #625831

#	Time	Username	Problem	Language	Result	Execution time	Memory
625831		Arsa	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	848 ms	5444 KiB

ho_t4

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

typedef long long ll;
typedef pair<ll,ll> pii;

const int N = 310;
const int M = 5e4+10;
const ll INF = 1e16;

ll n,m;
vector <ll> G[N];
vector <ll> vec[2];
ll dis[N][N][2];
ll path0, path1;
ll par[N];
bool hame[M][2];
ll ans;

void Input();
void Dijkstra(int,int,int);
void Halat0_0();
void Halat1_0();
void Halat0_1();
void Path_0();
void Path_1();

struct edge{
	ll u, v, w, c;		
};

edge e[M];

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	Input();
	
	Dijkstra(0, -1, 0);
	if(dis[0][n-1][0] != INF)
		Path_0();
	path0 = dis[0][n-1][0];
	
	Dijkstra(n-1, -1, 0);
	if(dis[n-1][0][0] != INF)
		Path_1();
	path1 = dis[n-1][0][0];
	
	ans = path0 + path1;
	
	for(int i = 1;i < n-1;i++)
		Dijkstra(i, -1, 0);
	
	Halat0_0();
	Halat0_1();
	Halat1_0();
	
	if(ans >= INF)
		cout << -1 << endl;
	else
		cout << ans << endl;	
}

void Input(){
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		ll u, v, w, c;
		cin >> u >> v >> w >> c, u--, v--;
		e[i].u = u, e[i].v = v, e[i].w = w, e[i].c = c;
		G[u].push_back(i), G[v].push_back(i);
	}
}

void Dijkstra(int s,int swp,int type){
	set<pii> st;
	bool mark[N];
	fill(mark, mark + n + 10, 0);
	
	for(int i = 0;i < n;i++)
		dis[s][i][type] = INF;
	dis[s][s][type] = 0, par[s] = -1;
	st.insert({0, s});
	
	while(st.size()){
		int a = st.begin() -> second;
		st.erase(st.begin());
		if(!mark[a]){
			mark[a] = true;
			for(auto i : G[a]){
				ll w = e[i].w, u = e[i].u, v = e[i].v; 
				if(a == u and i != swp){
					if(dis[s][v][type] > dis[s][u][type] + w)
						dis[s][v][type] = dis[s][u][type] + w, par[v] = i, st.insert({dis[s][v][type], v});	
				}else if(a == v and i == swp){
					if(dis[s][u][type] > dis[s][v][type] + w)
						dis[s][u][type] = dis[s][v][type] + w, par[u] = i, st.insert({dis[s][u][type], u});
				}
			}
		}
	}
}

void Path_0(){
	int v = n-1;
	while(par[v] != -1){
		vec[0].push_back(par[v]);
		hame[par[v]][0] = true;
		v = e[par[v]].u;
	}
}

void Path_1(){
	int v = 0;
	while(par[v] != -1){
		vec[1].push_back(par[v]);
		hame[par[v]][1] = true;
		v = e[par[v]].u;
	}
}

void Halat0_0(){
	for(int i = 0;i < m;i++){
		ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
		if(dis[0][v][0] + w + dis[u][n-1][0] < path0)
			if(dis[n-1][v][0] + w + dis[u][0][0] < path1)
				ans = min(ans, dis[0][v][0] + w + dis[u][n-1][0] + dis[n-1][v][0] + w + dis[u][0][0] + cost);
	}
}

void Halat0_1(){
	for(int i = 0;i < m;i++){
		ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
		if(dis[0][v][0] + w + dis[u][n-1][0] < path0){
			if(!hame[i][1])
				ans = min(ans, dis[0][v][0] + w + dis[u][n-1][0] + path1 + cost);
			else{
				Dijkstra(n-1, i, 1);
				ans = min(ans, dis[0][v][0] + w + dis[u][n-1][0] + dis[n-1][0][1] + cost);
			}
		}
	}
}

void Halat1_0(){
	for(int i = 0;i < m;i++){
		ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
		if(dis[n-1][v][0] + w + dis[u][0][0] < path1){
			if(!hame[i][0])
				ans = min(ans, dis[n-1][v][0] + w + dis[u][0][0]  + path0 + cost);
			else{
				Dijkstra(0, i, 1);
				ans = min(ans, dis[n-1][v][0] + w + dis[u][0][0]  + dis[0][n-1][1] + cost);
			}
		}
	}	
}

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