Submission #1326446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326446		joacru	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	472 ms	3256 KiB

ho_t4

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

const int INF = 1e9;

struct Edge{
	int u, v, w, d;
};

struct G{
	struct E{
		int v, w, i;
	};
	struct D{
		vector<int> dist;
		vector<int> back;
		D(int n): dist(n, INF), back(n, -1) {}
	};
	vector<vector<E>> g;
	G(int n): g(n) {}
	void add(int u, int v, int w, int i){
		g[u].push_back({v,w,i});
	}
	void pop(int u){ // Eliminar arista agregada temporalmente
		g[u].pop_back();
	}
	D dijkstra(int s, int p){ // source y prohibida (-1 si no hay)
		D ret(SZ(g));
		priority_queue<pair<int,int>> dij;
		ret.dist[s] = 0;
		dij.push({0, s});
		while(SZ(dij)){
			int d = -dij.top().first, u = dij.top().second;
			dij.pop();
			if(ret.dist[u] != d) continue;
			for(auto [v, w, i]: g[u]){
				if(i == p) continue;
				int nd = d + w;
				if(nd < ret.dist[v]){
					ret.dist[v] = nd;
					ret.back[v] = i;
					dij.push({-nd, v});
				}
			}
		}
		return ret;
	}
};

void solve(){
	
	int n, m;
	cin>>n>>m;
	
	vector<Edge> es(m);
	
	for(Edge &e: es) cin>>e.u>>e.v>>e.w>>e.d;
	
	G g(n+1), h(n+1);
	
	forn(i,m){
		g.add(es[i].u, es[i].v, es[i].w, i);
		h.add(es[i].v, es[i].u, es[i].w, i);
	}
	
	G::D fromS = g.dijkstra(1,-1);
	G::D fromN = g.dijkstra(n,-1);
	G::D toS = h.dijkstra(1,-1);
	G::D toN = h.dijkstra(n,-1);
	
	//~ DBG(fromS.dist);
	//~ DBG(toN.dist);
	//~ DBG(fromN.dist);
	//~ DBG(toS.dist);
	
	set<int> pathSN, pathNS;
	{
		int a = 1, b = n;
		forn(_,2){
			while(fromS.back[b] != -1){
				int i = fromS.back[b];
				pathSN.insert(i);
				b = es[i].u;
			}
			swap(a,b);
			swap(fromS,fromN);
			swap(pathSN,pathNS);
		}
	}
	
	// TODO: Cambiar cositas a ll
	
	ll costSN = fromS.dist[n];
	ll costNS = fromN.dist[1];
	//~ DBG2(costSN, costNS);
	
	ll ans = min((ll) INF, costSN + costNS);
	
	forn(i,m){
		int u = es[i].u, v = es[i].v, w = es[i].w, d = es[i].d;
		ll auxSN = costSN;
		ll auxNS = costNS;
		if(pathSN.count(i)){
			auxSN = INF;
			// TODO: Recalcular camino
			g.add(v, u, w, -1);
			G::D fromSTemp = g.dijkstra(1, i);
			g.pop(v);
			auxSN = fromSTemp.dist[n];
		} else{
			auxSN = min(auxSN, (ll)fromS.dist[v] + es[i].w + toN.dist[u]);
		}
		if(pathNS.count(i)){
			auxNS = INF;
			// TODO: Recalcular camino
			g.add(v, u, w, -1);
			G::D fromNTemp = g.dijkstra(n, i);
			g.pop(v);
			auxNS = fromNTemp.dist[1];
		} else{
			auxNS = min(auxNS, (ll)fromN.dist[v] + es[i].w + toS.dist[u]);
		}
		ll aux = auxSN + auxNS + d;
		//~ if(i == 0){
			//~ DBG4(i, auxSN, auxNS, d);
			//~ DBG3(fromN.dist[v], es[i].w, toS.dist[u]);
		//~ }
		ans = min(ans, aux);
	}
	
	if(ans == INF) ans = -1;
	cout<<ans<<"\n";
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("input.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	return 0;
}

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