제출 #203191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203191		ZwariowanyMarcin	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	105 ms	8592 KiB

ho_t4

#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)

using namespace std;

const int nax = 50005;
const LL INF = 1e18;

int n, m;
int e[nax], f[nax], c[nax], d[nax];

bool na[nax];

multiset <pair<LL, int>> s[210][210];

LL cost[210][210];

pair <LL, int> dp[210][210];
LL dp2[210][210];

vector <int> path;
vector <int> ind;

void add(int x) {
	if (ss(path) && path.back() == x) return;
	path.pb(x);
}

void gao(int a, int b) {
	assert(a != b);
	if (dp[a][b].fi == cost[a][b]) {
		add(a);
		add(b);
		return;
	}
	gao(a, dp[a][b].se);
	gao(dp[a][b].se, b);
}

LL out[nax];
LL in[nax];
LL fe;

void solve(int skad, int dokad) {
	rep(i, 1, n) rep(j, 1, n) {
		s[i][j].clear();
		cost[i][j] = INF;
	}
	
	rep(i, 1, m) {
		s[e[i]][f[i]].insert({c[i], i});
		cost[e[i]][f[i]] = min(cost[e[i]][f[i]], (LL) c[i]);
		na[i] = 0;
		in[i] = INF;
	}
	rep(i, 1, n)
		rep(j, 1, n) {
			if (i == j) dp[i][j] = {0LL, 0};
			else if (!s[i][j].empty()) dp[i][j] = {s[i][j].begin()->fi, 0};
			else dp[i][j] = {INF, 0};
		}
		
	rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) 
		dp[i][j] = min(dp[i][j], {dp[i][k].fi + dp[k][j].fi, k});
		
	fe += dp[skad][dokad].fi;
	
	path.clear();
	ind.clear();
	
	if (dp[skad][dokad].fi != INF) {
		gao(skad, dokad);
	}
	
	for (int i = 0; i + 1 < ss(path); ++i) {
		int a = path[i];
		int b = path[i + 1];
		int id = s[a][b].begin()->se;
		s[a][b].erase(s[a][b].begin());
		na[id] = 1;
		ind.pb(id);
	}
	
	rep(i, 1, n) rep(j, 1, n) {
		if (i == j) dp2[i][j] = 0LL;
		else if(ss(s[i][j])) dp2[i][j] = s[i][j].begin()->fi;
		else dp2[i][j] = INF;
	}
	
	rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) 
		dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j]);
	
	rep(i, 1, m) {
		if (!na[i]) {
			out[i] += min(dp[skad][dokad].fi, c[i] + dp[skad][f[i]].fi + dp[e[i]][dokad].fi);
		}
	}
	
	for (int i = 0; i < ss(path); ++i)
		for (int j = i + 1; j < ss(path); ++j) {
			int a = path[i];
			int b = path[j];
			LL val = dp2[a][b] + dp[skad][a].fi + dp[b][dokad].fi;
			for (int k = i; k < j; ++k)
				in[ind[k]] = min(in[ind[k]], val);
		}
		
	rep(i, 1, m) 
		if (na[i])
			out[i] += in[i];	
}

int main() {		
	scanf ("%d%d", &n, &m);
	rep(i, 1, m) {
		scanf ("%d%d%d%d", e + i, f + i, c + i, d + i);
	}
	
	solve(1, n);
	solve(n, 1);
	
	LL best = fe;
	rep(i, 1, m) best = min(best, out[i] + d[i]);
	if (best >= INF) printf ("-1\n");
	else printf ("%lld", best);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:123:8: 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:125:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d%d", e + i, f + i, c + i, d + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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