제출 #534870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534870		Haruto810198	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	49 ms	1860 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 dis1[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;
	}
	
	// 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. dis1, dis2
	FOR(i, 1, n, 1){
		FOR(j, 1, n, 1){
			dis1[i][j] = dis2[i][j] = LNF;
		}
		dis1[i][i] = dis2[i][i] = 0;
	}
	
	FOR(e, 1, m, 1){
		int u = from[e], v = to[e];
		dis1[u][v] = min(dis1[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){
				dis1[i][j] = min(dis1[i][j], dis1[i][k] + dis1[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)
	
	Dijkstra(s, t);
	FloydWarshall();
	
	// e not on sp
	FOR(e, 1, m, 1){
		if(isspe[e]) continue;
		int u = from[e], v = to[e];
		res[e] += min(dis1[s][t], dis1[s][v] + c[e] + dis1[u][t]);
	}
 
	// e on sp
	int sz = szof(spe);
	
	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, dis1[s][u] + dis2[u][v] + dis1[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);
	}
	
	// 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 = dis1[1][n] + dis1[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';
	
	assert(RES < LNF); //

	return 0;
	
}

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