Submission #201230

#	Time	Username	Problem	Language	Result	Execution time	Memory
201230		ainta	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	52 ms	3756 KiB

ho_t4

#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 2010
#define pli pair<long long,int>
using namespace std;
vector<int>E[N_], F[N_], G[N_];
vector<int>L[N_], Num[N_];
int n, m, Path[N_], chk[101000];
int SP[N_], EP[N_], imp[N_], H[N_], vv[N_];
long long SD[N_], ED[N_], D[N_], DD[101000][2], INF = 1e18, U[N_];

int ord[N_];

priority_queue<pli>PQ;
struct Edge {
	int a, b, c, d;
}Ed[101000];
void Push(int a, int p, long long c) {
	if (D[a] <= c)return;
	D[a] = c;
	Path[a] = p;
	PQ.push({ -c,a });
}
void Dijk(int a) {
	int i;
	for (i = 1; i <= n; i++)D[i] = INF, Path[i] = 0, vv[i] = 0;
	Push(a, 0, 0);
	while (!PQ.empty()) {
		pli tp = PQ.top();
		PQ.pop();
		int x = tp.second;
		if (vv[x])continue;
		vv[x] = 1;
		for (int i = 0; i < E[x].size(); i++) {
			Push(E[x][i], Num[x][i], D[x] + L[x][i]);
		}
	}
}
int cnt;
void DFS(int a, int pp) {
	int i;
	if (imp[a]) {
		H[a] = a;
		ord[a] = cnt--;
	}
	else H[a] = H[pp];
	for (auto &x : G[a]) {
		DFS(x, a);
	}
}
void Do(int st, int ed, int ck) {
	int i, j;

	for (i = 1; i <= n; i++) {
		G[i].clear();
		E[i].clear();
		F[i].clear();
		L[i].clear();
		Num[i].clear();
	}

	for (i = 1; i <= m; i++) {
		E[Ed[i].a].push_back(Ed[i].b);
		L[Ed[i].a].push_back(Ed[i].c);
		Num[Ed[i].a].push_back(i);
	}

	Dijk(st);
	long long d = D[ed];
	DD[0][ck] = d;
	for (i = 1; i <= n; i++) SD[i] = D[i];


	for (i = 1; i <= n; i++) {
		E[i].clear();
		L[i].clear();
		Num[i].clear();
	}

	for (i = 1; i <= m; i++) {
		E[Ed[i].b].push_back(Ed[i].a);
		L[Ed[i].b].push_back(Ed[i].c);
		Num[Ed[i].b].push_back(i);
	}

	Dijk(ed);

	for (i = 1; i <= n; i++) {
		ED[i] = D[i];
		EP[i] = Path[i];
		H[i] = imp[i] = 0;
	}
	for (i = 1; i <= n; i++) {
		if(EP[i])G[Ed[EP[i]].b].push_back(i);
	}
	for (i = 1; i <= m; i++)chk[i] = 0;
	int x = st;
	imp[st] = imp[ed] = 1;
	if (d < INF) {
		while (x != ed) {
			imp[x] = 1;
			int t = EP[x];
			chk[t] = 1;
			x = Ed[t].b;
		}
	}
	for (i = 1; i <= m; i++) {
		if (!chk[i]) {
			DD[i][ck] = SD[Ed[i].b] + ED[Ed[i].a] + Ed[i].c;
			DD[i][ck] = min(DD[i][ck], d);
		}
		else DD[i][ck] = INF;
	}
	for (i = 1; i <= n; i++)U[i] = INF;
	cnt = n;
	DFS(ed, 0);
	for (i = 1; i <= m; i++) {
		if (chk[i])continue;
		int a = H[Ed[i].a], b = H[Ed[i].b];
		if (ord[a] < ord[b]) {
			long long t = SD[Ed[i].a] + ED[Ed[i].b] + Ed[i].c;
			for (j = ord[a]; j < ord[b]; j++) {
				U[j] = min(U[j], t);
			}
		}
	}
	for (i = 1; i <= m; i++) {
		if (!chk[i])continue;
		int a = ord[Ed[i].a], b = ord[Ed[i].b];
		if (a > b)swap(a, b);
		DD[i][ck] = min(DD[i][ck],U[a]);
	}
}
int main() {
	int i, j;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		Ed[i] = { a,b,c,d };
	}
	Do(1, n, 0);
	Do(n, 1, 1);
	long long res = INF;
	for (i = 0; i <= m; i++) {
		res = min(res, DD[i][0] + DD[i][1] + Ed[i].d);
	}
	if (res > 8e17)res = -1;
	printf("%lld\n", res);
}

Compilation message (stderr)

ho_t4.cpp: In function 'void Dijk(int)':
ho_t4.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < E[x].size(); i++) {
                   ~~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void DFS(int, int)':
ho_t4.cpp:42:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:136:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
ho_t4.cpp:137:7: 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:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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