Submission #204192

#	Time	Username	Problem	Language	Result	Execution time	Memory
204192		kig9981	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	646 ms	3576 KiB

ho_t4

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

vector<tuple<int,int,int>> adj[200], radj[200];
vector<tuple<int,int,int,int,int>> E;
int N, P[200];
long long dist1[200], dist2[200], rdist1[200], rdist2[200], dist[200];
bool MP[2][50000];

void dijkstra(int c, long long *dist, vector<tuple<int,int,int>> *adj)
{
	priority_queue<pair<long long,int>> Q;
	for(int i=0;i<N;i++) {
		dist[i]=(i!=c)*0x1f1f1f1f1f1f1f1fLL;
		P[i]=-1;
	}
	Q.emplace(0,c);
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		if(-t!=dist[c]) continue;
		for(auto[n,w,i]: adj[c]) if(dist[n]>dist[c]+w) {
			dist[n]=dist[c]+w;
			P[n]=i;
			Q.emplace(-dist[n],n);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int M;
	long long ans;
	priority_queue<pair<long long,int>> Q;
	cin>>N>>M;
	E.resize(M);
	for(int i=0;i<M;i++) {
		auto &[u,v,w,x,idx]=E[i];
		cin>>u>>v>>x>>w; idx=i;
		adj[--u].emplace_back(--v,x,i);
		radj[v].emplace_back(u,x,i);
	}
	dijkstra(N-1,dist2,radj); dijkstra(0,dist1,adj);
	for(int c=0;c<N;c++) if(P[c]>-1) MP[0][P[c]]=true;
	dijkstra(0,rdist2,radj); dijkstra(N-1,rdist1,adj);
	for(int c=0;c<N;c++) if(P[c]>-1) MP[1][P[c]]=true;
	ans=dist1[N-1]+rdist1[0];
	for(auto[u,v,w,x,i]: E) {
		long long res=w;
		if(MP[0][i]) {
			for(int i=0;i<N;i++) dist[i]=(i!=0)*0x1f1f1f1f1f1f1f1fLL;
			Q.emplace(0,0);
			while(!Q.empty()) {
				auto[t,c]=Q.top();
				Q.pop();
				if(-t!=dist[c]) continue;
				if(c==v && dist[u]>dist[v]+x) {
					dist[u]=dist[v]+x;
					Q.emplace(-dist[u],u);
				}
				for(auto[n,w,j]: adj[c]) if(i!=j && dist[n]>dist[c]+w) {
					dist[n]=dist[c]+w;
					Q.emplace(-dist[n],n);
				}
			}
			res+=dist[N-1];
		}
		else res+=min(dist1[N-1],dist1[v]+dist2[u]+x);
		if(MP[1][i]) {
			for(int i=0;i<N;i++) dist[i]=(i!=N-1)*0x1f1f1f1f1f1f1f1fLL;
			Q.emplace(0,N-1);
			while(!Q.empty()) {
				auto[t,c]=Q.top();
				Q.pop();
				if(-t!=dist[c]) continue;
				if(c==v && dist[u]>dist[v]+x) {
					dist[u]=dist[v]+x;
					Q.emplace(-dist[u],u);
				}
				for(auto[n,w,j]: adj[c]) if(i!=j && dist[n]>dist[c]+w) {
					dist[n]=dist[c]+w;
					Q.emplace(-dist[n],n);
				}
			}
			res+=dist[0];
		}
		else res+=min(rdist1[0],rdist1[v]+rdist2[u]+x);
		ans=min(ans,res);
	}
	cout<<(ans<0x1f1f1f1f1f1f1f1fLL ? ans:-1)<<'\n';
	return 0;
}

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