Submission #666536

#	Time	Username	Problem	Language	Result	Execution time	Memory
666536		kinope	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	338 ms	13332 KiB

ho_t4

#include <bits/stdc++.h>
#define ff first
#define ss second
#define int unsigned
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
struct st{int a, b, c; ll d;} kraw[50000];

vector<int> g[201][2];
int C[201][201][2], n;
int odl[4][201][201]; //0. to z 1 do innych, 1. to z n do innych, 2. to z innych do 1, 3. to z innych do n
bool odw[201];

void dijkstra(int s, int y, int b, bool ODWR){
		for(int i = 1; i <= n; ++i) odw[i] = 0;
		odw[y] = 1;
		odl[b][s][y] = 0;
		for(int x = 1; x <= n; ++x){
				int u=0; ll dis = 2e09;
				for(int j = 1; j <= n; ++j){
						if(odw[j]) continue;
						if(dis > odl[b][j][y]) u = j, dis = odl[b][j][y];
				}
				if(!u) return;
				odw[u] = 1;
				for(int j = 1; j <= n; ++j){
						if(odw[j]) continue;
						odl[b][j][y] = min(odl[b][j][y], odl[b][u][y] + C[u][j][ODWR]);
				}
		}
}

void read(int &a){
		a = 0; char c = getchar_unlocked();
		while(c<'0'||'9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-48, c = getchar_unlocked();
}
void readll(ll &a){
		a = 0; char c = getchar_unlocked();
		while(c<'0'||'9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-48, c = getchar_unlocked();
}

signed main(){
		int m, a, b, c; ll d;
		read(n); read(m);
		for(int i = 0; i <= n; ++i)
				for(int j = 0; j <= n; ++j) odl[0][i][j] = odl[1][i][j] = odl[2][i][j] = odl[3][i][j] = C[i][j][0] = C[i][j][1] = 2e09;
		
		for(int i = 0; i < m; ++i){
				read(a); read(b); read(c); readll(d);
				kraw[i] = {a, b, c, d};
				if(C[a][b][0] == 2e09) g[a][0].emplace_back(b);
				if(C[b][a][1] == 2e09) g[b][1].emplace_back(a);
				C[a][b][0] = min(C[a][b][0], c);
				C[b][a][1] = min(C[b][a][1], c);
		}
		
		for(int j = 0; j <= n; ++j) odl[0][1][j] = odl[1][n][j] = odl[2][1][j] = odl[3][n][j] = 0;
		
		for(int i = 2; i <= n; ++i){
				if(g[i][1].empty()) continue;
				dijkstra(1, i, 0, 0);
		} dijkstra(1, 0, 0, 0);
		for(int i = 1; i < n; ++i) {
				if(g[i][1].empty()) continue;
				dijkstra(n, i, 1, 0);
		} dijkstra(n, 0, 1, 0); 
		for(int i = 2; i <= n; ++i) dijkstra(1, i, 2, 1);
		for(int i = 1; i < n; ++i) dijkstra(n, i, 3, 1); 
		multiset<int> s[201][4]; //0. to z 1 do x, 1. to z n do x, 2. to z x do 1, 3. to z x do n
		
		for(int i = 0; i < m; ++i){
				a = kraw[i].a, b = kraw[i].b, c = kraw[i].c;
				s[b][0].emplace(odl[0][a][b] + c);
				s[b][1].emplace(odl[1][a][b] + c);
				s[a][2].emplace(odl[2][b][a] + c);
				s[a][3].emplace(odl[3][b][a] + c);
		}
		
		ll wynik = 2e09;
		
		for(int i = 0; i < m; ++i){
				a = kraw[i].a, b = kraw[i].b, c = kraw[i].c, d = kraw[i].d;
				
				int tmp = c + odl[0][a][b];
				multiset<int>::iterator it = s[b][0].find(tmp); s[b][0].erase(it);
				tmp = c + odl[1][a][b];
				it = s[b][1].find(tmp); s[b][1].erase(it);
				
				tmp = c + odl[2][a][b]; s[b][2].emplace(tmp);
				tmp = c + odl[3][a][b]; s[b][3].emplace(tmp);
				
				ll t0 = 2e09, t1 = 2e09, t2 = *s[b][2].begin(), t3 = *s[b][3].begin();
				if(s[b][0].size()) t0 = *s[b][0].begin();
				if(s[b][1].size()) t1 = *s[b][1].begin();
				
				if(b == 1) t0 = t2 = 0;
				if(b == n) t1 = t3 = 0;
				
				wynik = min(wynik, (ll) t0 + t3 + t1 + t2 + d);
				wynik = min(wynik, (ll) t0 + t3 + odl[1][1][b] + d);
				wynik = min(wynik, (ll) odl[0][n][b] + t1 + t2 + d);
				
				tmp = c + odl[2][a][b];
				it = s[b][2].find(tmp); s[b][2].erase(it);
				tmp = c + odl[3][a][b];
				it = s[b][3].find(tmp); s[b][3].erase(it);
				
				tmp = c + odl[0][a][b]; s[b][0].emplace(tmp);
				tmp = c + odl[1][a][b]; s[b][1].emplace(tmp);
		}
		wynik = min(wynik, (ll) odl[0][n][0] + odl[1][1][0]);
		
		if(wynik != 2e09) printf("%lld\n", wynik);
		else printf("-1");
		
		return 0;
}

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