제출 #447961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447961		maomao90	Olympic Bus (JOI20_ho_t4)	C++17	32 / 100	260 ms	2496 KiB

ho_t4

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 205
#define MAXM 50005

int n, m;
ll g[MAXN][MAXN], sg[MAXN][MAXN];
int u[MAXM], v[MAXM], c[MAXM], d[MAXM];
ll rdist[MAXN][MAXN];

bool visited[MAXN];
bool onshot[MAXN][MAXN];
ll dist[MAXN][MAXN];
void dij(int s, bool up = 0) {
	REP (i, 1, n + 1) {
		dist[s][i] = LINF;
		visited[i] = 0;
	}
	dist[s][s] = 0;
	REP (_, 0, n) {
		ll u = -1, mn = LINF;
		REP (i, 1, n + 1) {
			if (!visited[i] && mnto(mn, dist[s][i])) {
				u = i;
			}
		}
		if (u == -1) break;
		visited[u] = 1;
		REP (i, 1, n + 1) {
			if (mnto(dist[s][i], dist[s][u] + g[u][i]) && up) {
				onshot[u][i] = 1;
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	REP (i, 1, n + 1) {
		REP (j, 1, n + 1) {
			g[i][j] = LINF;
			sg[i][j] = LINF;
			rdist[i][j] = LINF;
		}
		g[i][i] = 0;
		sg[i][i] = 0;
	}
	REP (i, 0, m) {
		scanf("%d%d%d%d", &u[i], &v[i], &c[i], &d[i]);
		if (c[i] <= g[u[i]][v[i]]) {
			sg[u[i]][v[i]] = g[u[i]][v[i]];
			g[u[i]][v[i]] = c[i];
		} else {
			mnto(sg[u[i]][v[i]], (ll) c[i]);
		}
	}
	REP (i, 1, n + 1) {
		REP (j, 1, n + 1) {
			rdist[i][j] = g[i][j];
		}
	}
	REP (k, 1, n + 1) {
		REP (i, 1, n + 1) {
			REP (j, 1, n + 1) {
				mnto(rdist[i][j], rdist[i][k] + rdist[k][j]);
			}
		}
	}
	dij(1, 1);
	dij(n, 1);
	ll ans = dist[1][n] + dist[n][1];
	int cnt = 0;
	REP (i, 0, m) {
		ll fi = min(dist[1][n], rdist[1][v[i]] + rdist[u[i]][n] + c[i]),
		   se = min(dist[n][1], rdist[n][v[i]] + rdist[u[i]][1] + c[i]);
		debug("%d %d: %lld %lld\n", u[i], v[i], fi, se);
		if (sg[u[i]][v[i]] != g[u[i]][v[i]] && onshot[u[i]][v[i]] &&
			   	g[u[i]][v[i]] == c[i]) {
			cnt++;
			g[u[i]][v[i]] = sg[u[i]][v[i]];
			ll tmp = g[v[i]][u[i]];
			mnto(g[v[i]][u[i]], (ll) c[i]);
			dij(1);
			dij(n);
			fi = dist[1][n];
			se = dist[n][1];
			g[u[i]][v[i]] = c[i];
			g[v[i]][u[i]] = tmp;
			dij(1);
			dij(n);
		}
		debug("%lld %lld\n", fi, se);
		mnto(ans, fi + se + d[i]);
	}
	assert(cnt <= 2 * n);
	if (ans < LINF) {
		printf("%lld\n", ans);
	} else {
		printf("-1\n");
	}
	return 0;
}

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

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

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