Submission #534840

#	Time	Username	Problem	Language	Result	Execution time	Memory
534840		Haruto810198	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	34 ms	1868 KiB

ho_t4

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = 1e18;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 210;

int n, m;

int from[MAX], to[MAX], c[MAX], d[MAX]; // information of edges
vi edge[MAX];

vi spe; // edges on shortest path s -> t
bool isspe[MAX];

int dis[MAX][MAX], dis2[MAX][MAX]; // dis2 : dis. without using edges in sp
int res[MAX]; // res[i] = optimal answer if we choose to reverse edge i

void Dijkstra(int s, int t){
	
	int disDij[MAX];
	bool vis[MAX];
	int pv[MAX], pe[MAX]; // id. of previous vertex, edge
	FOR(i, 1, n, 1){
		disDij[i] = LNF + 1;
		vis[i] = 0;
	}
	disDij[s] = 0;

	FOR(owo, 1, n, 1){
		
		int Min = LNF, u = 0;
		FOR(i, 1, n, 1){
			if(vis[i] == 0 and Min > disDij[i]){
				Min = disDij[i];
				u = i;
			}
		}
		
		for(int e : edge[u]){
			int v = to[e];
			if(disDij[u] + c[e] < disDij[v]){
				disDij[v] = disDij[u] + c[e];
				pv[v] = u;
				pe[v] = e;
			}
		}

		vis[u] = 1;
		/*	
		cerr<<"dis : ";
		FOR(i, 1, n, 1){
			if(disDij[i] > 100) cerr<<"- ";
			else cerr<<disDij[i]<<" ";
		}
		cerr<<endl;
		*/
	}
	
	// find shortest path s -> t
	spe.clear();
	FOR(i, 1, m, 1){
		isspe[i] = 0;
	}

	int ptr = t;

	while(ptr != s){
		spe.pb(pe[ptr]);
		isspe[pe[ptr]] = 1;
		ptr = pv[ptr];
	}

	reverse(spe.begin(), spe.end());
	assert(!spe.empty());

}

void FloydWarshall(){
	
	// init. dis, dis2
	FOR(i, 1, n, 1){
		FOR(j, 1, n, 1){
			dis[i][j] = dis2[i][j] = LNF;
		}
		dis[i][i] = dis2[i][i] = 0;
	}
	
	FOR(e, 1, m, 1){
		int u = from[e], v = to[e];
		dis[u][v] = min(dis[u][v], c[e]);
		if(!isspe[e]) dis2[u][v] = min(dis2[u][v], c[e]);
	}
	
	FOR(k, 1, n, 1){
		FOR(i, 1, n, 1){
			FOR(j, 1, n, 1){
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
				dis2[i][j] = min(dis2[i][j], dis2[i][k] + dis2[k][j]);
			}
		}
	}

}

void solve(int s, int t){
	
	// (s, t) = (1, n) or (n, 1)
	
	//cerr<<"solve "<<s<<" -> "<<t<<endl;
	Dijkstra(s, t);
	//cerr<<"Dij : ok"<<endl;
	FloydWarshall();
	//cerr<<"FW : ok"<<endl;
	
	// e not on sp
	FOR(e, 1, m, 1){
		if(isspe[e]) continue;
		int u = from[e], v = to[e];
		res[e] += min(dis[s][t], dis[s][v] + c[e] + dis[u][t]);
	}

	// e on sp
	int sz = szof(spe);
	
	//
	FOR(i, 0, sz-2, 1){
		assert(to[spe[i]] == from[spe[i+1]]);
	}
	//

	FOR(i, 0, sz-1, 1){
		int e = spe[i];
		int Min = LNF;

		FOR(j, 0, i, 1){
			FOR(k, i, sz-1, 1){
				int u = from[spe[j]], v = to[spe[k]];
				Min = min(Min, dis[s][u] + dis2[u][v] + dis[v][t]);
			}
		}

		res[e] += Min;
	}
}

signed main(){
	
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>m;
	FOR(i, 1, m, 1){
		cin>>from[i]>>to[i]>>c[i]>>d[i];
		edge[from[i]].pb(i);
	}
	//cerr<<"in : ok"<<endl;
	
	// build 2 extra edges to guarantee there is a path 1 -> n, n -> 1
	from[m+1] = 1, from[m+2] = n;
	to[m+1] = n, to[m+2] = 1;
	c[m+1] = c[m+2] = LNF;
	d[m+1] = d[m+2] = LNF;
	edge[1].pb(m+1);
	edge[n].pb(m+2);
	m += 2;

	solve(1, n);
	solve(n, 1);

	int RES = dis[1][n] + dis[n][1]; // don't flip edges
	FOR(e, 1, m, 1){
		res[e] += d[e];
		RES = min(RES, res[e]); // flip e
	}

	if(RES < LNF) cout<<RES<<'\n';
	else cout<<-1<<'\n';
	
	// subtask 2
	FOR(i, 1, m-2, 2){
		assert(res[i] == res[i+1]);
	}

	return 0;
	
}

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