Submission #202612

#	Time	Username	Problem	Language	Result	Execution time	Memory
202612		dndhk	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	976 ms	3064 KiB

ho_t4

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

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

const int MAX_N = 200;
const int MAX_M = 50000;
const ll INF = 1e14;

int N, M;
vector<pii> gp[2][MAX_N+1];
int u[MAX_M+1], v[MAX_M+1];
ll d[MAX_M+1], c[MAX_M+1];
ll dp[2][2][MAX_N+1];

ll ans;
vector<int> vt;

int ST;

priority_queue<pll, vector<pll>, greater<pll> > pq;

bool vst[MAX_N+1];
int from[MAX_N+1];

void solve(int x, int y){
	for(int i=1; i<=N; i++){
		dp[x][y][i] = INF;
		vst[i] = false;
		from[i] = 0;
	}
	dp[x][y][ST] = 0;
	pq.push({0LL, (ll)ST});
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		if(from[now.second]!=0 && x==0){
			vt.pb(from[now.second]);
		}
		for(pii p : gp[x][now.second]){
			if(dp[x][y][p.first]>dp[x][y][now.second] + c[p.second]){
				from[p.first] = p.second;
				dp[x][y][p.first] = dp[x][y][now.second] + c[p.second];
				pq.push({dp[x][y][p.first], p.first});
			}
		}
	}
}

bool chk[MAX_M+1];

vector<pii> gp2[MAX_N+1];

ll dp2[MAX_N+1], dp3[MAX_N+1];

void solve2(int x){
	for(int i=1; i<=N; i++){
		//while(!gp2[i].empty())	gp2[i].pop_back();
		dp2[i] = dp3[i] = INF;
		vst[i] = false;
	}
	/*for(int i=1; i<=M; i++){
		if(i!=x){
			gp2[u[i]].pb({v[i], (int)c[i]});
		}else{
			gp2[v[i]].pb({u[i], (int)c[i]});
		}
	}*/
	gp[0][v[x]].pb({u[x], x});
	pq.push({0LL, 1LL});
	dp2[1] = 0;
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		for(pii p : gp[0][now.second]){
			if(now.second==u[x] && p.second==x)	continue;
			if(dp2[p.first]>dp2[now.second] + c[p.second]){
				dp2[p.first] = dp2[now.second] + c[p.second];
				pq.push({dp2[p.first], p.first});
			}
		}
	}
	for(int i=1; i<=N; i++)	vst[i] = false;
	pq.push({0LL, (ll)N});
	dp3[N] = 0;
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		for(pii p : gp[0][now.second]){
			if(now.second==u[x] && p.second==x)	continue;
			if(dp3[p.first]>dp3[now.second] + c[p.second]){
				dp3[p.first] = dp3[now.second] + c[p.second];
				pq.push({dp3[p.first], p.first});
			}
		}
	}
	gp[0][v[x]].pop_back();
	//cout<<x<<" "<<dp2[N]<<" "<<dp3[1]<<" "<<d[x]<<endl;
	ans = min(ans, dp2[N] + dp3[1] + d[x]);
}


int main(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++){
		scanf("%d%d%lld%lld", &u[i], &v[i], &c[i], &d[i]);
		gp[0][u[i]].pb({v[i], i});
		gp[1][v[i]].pb({u[i], i});
	}
	ST = 1; solve(0, 0); ST = N; solve(0, 1);
	ST = 1; solve(1, 0); ST = N; solve(1, 1);
	ans = dp[0][0][N] + dp[0][1][1];
	for(int i : vt){
		if(!chk[i]){
			solve2(i);
			chk[i] = true;
		}
	}
	/*for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			for(int k=1; k<=N; k++){
				cout<<dp[i][j][k]<<" ";
			}
			cout<<endl;
		}
	}*/
	
	for(int i=1; i<=M; i++){
		if(!chk[i]){
			//solve2(i);
			ll dist = d[i];
			if(dp[0][0][u[i]]<=dp[0][0][v[i]]+c[i])	dist+=dp[0][0][N];
			else	dist+=min(dp[0][0][N], dp[0][0][v[i]] + c[i] + dp[1][1][u[i]]);
			if(dp[0][1][u[i]]<=dp[0][1][v[i]]+c[i])	dist+=dp[0][1][1];
			else	dist+=min(dp[0][1][1], dp[0][1][v[i]] + c[i] + dp[1][0][u[i]]);
			// cout<<u[i]<<" "<<v[i]<<" "<<c[i]<<" "<<d[i]<<endl;
			// cout<<dp[0][0][v[i]]<<" "<<dp[1][1][u[i]]<<" "<<dp[0][1][v[i]]<<" "<<dp[1][0][u[i]]<<endl;
			ans = min(ans, dist);
		}
	}
	if(ans>=INF){
		printf("-1");
	}else{
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld", &u[i], &v[i], &c[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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