제출 #332600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332600		ChrisT	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	427 ms	7248 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
const int MN = 203;
struct Edge {
	int u,v,c,d;
};
set<pair<int,int>> adj[MN][MN];
int dist1[MN][MN], distN[MN][MN], dist12[MN][MN], distN2[MN][MN], p[MN], n;
vector<int> e1 = {-1},eN = {-1}, e12={-1}, eN2={-1};
void dijkstra (int *dist, int src) {
	memset(dist,0x3f,sizeof(int) * MN); memset(p,-1,sizeof p);
	dist[src] = 0;
	p[src] = -1;
	vector<bool> vis(n+1);
	while (true) {
		int cur = -1;
		for (int i = 1; i <= n; i++) if (!vis[i] && dist[i] < 1e9 && (cur == -1 || dist[i] < dist[cur])) cur = i;
		if (!~cur) break;
		vis[cur] = 1;
		for (int i = 1; i <= n; i++) if (!adj[cur][i].empty()) {
			int att = dist[cur] + adj[cur][i].begin()->first;
			if (att < dist[i]) {
				dist[i] = att;
				p[i] = adj[cur][i].begin()->second;
			}
		}
	}
} 
int main () {
	int m;
	scanf ("%d %d",&n,&m);
	vector<Edge> edges(m);
	for (int i = 0; i < m; i++) {
		Edge &e = edges[i];
		scanf ("%d %d %d %d",&e.u,&e.v,&e.c,&e.d);
		adj[e.u][e.v].emplace(e.c,i);
	}
	dijkstra(dist1[0],1);
	for (int i = 1; i <= n; i++) if (~p[i]) e1.push_back(p[i]);
	for (int i = 1; i < (int)e1.size(); i++) {
		Edge &e = edges[e1[i]];
		adj[e.u][e.v].erase({e.c,e1[i]});
		dijkstra(dist1[i],1);
		adj[e.u][e.v].emplace(e.c,e1[i]);
	}
	dijkstra(distN2[0],n);
	for (int i = 1; i <= n; i++) if (~p[i]) eN2.push_back(p[i]);
	for (int i = 1; i < (int)eN2.size(); i++) {
		Edge &e = edges[eN2[i]];
		adj[e.u][e.v].erase({e.c,eN2[i]});
		dijkstra(distN2[i],n);
		adj[e.u][e.v].emplace(e.c,eN2[i]);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			adj[i][j].clear();
	for (int i = 0; i < m; i++) {
		Edge &e = edges[i];
		adj[e.v][e.u].emplace(e.c,i);
	}
	dijkstra(distN[0],n);
	for (int i = 1; i <= n; i++) if (~p[i]) eN.push_back(p[i]);
	for (int i = 1; i < (int)eN.size(); i++) {
		Edge &e = edges[eN[i]];
		adj[e.v][e.u].erase({e.c,eN[i]});
		dijkstra(distN[i],n);
		adj[e.v][e.u].emplace(e.c,eN[i]);
	}
	dijkstra(dist12[0],1);
	for (int i = 1; i <= n; i++) if (~p[i]) e12.push_back(p[i]);
	for (int i = 1; i < (int)e12.size(); i++) {
		Edge &e = edges[e12[i]];
		adj[e.v][e.u].erase({e.c,e12[i]});
		dijkstra(dist12[i],1);
		adj[e.v][e.u].emplace(e.c,e12[i]);
	}
	int ret = dist1[0][n] + distN2[0][1];
	if (ret > 1e9) ret = 2e9;
	for (int i = 0; i < m; i++) {
		//want: dist(1,e.v) without edge i + dist(e.u,n) without edge i + e.d
		Edge &e = edges[i];
		int A = dist1[0][e.v], B = distN[0][e.u], C = distN2[0][e.v], D = dist12[0][e.u], E = dist1[0][n], F = distN2[0][1];
		for (int j = 1; j < (int)e1.size(); j++) if (e1[j] == i) {
			A = dist1[j][e.v];
			E = dist1[j][n];
		}
		for (int j = 1; j < (int)eN.size(); j++) if (eN[j] == i) {
			B = distN[j][e.u];
		}
		for (int j = 1; j < (int)eN2.size(); j++) if (eN2[j] == i) {
			C = distN2[j][e.v];
			F = distN2[j][1];
		}
		for (int j = 1; j < (int)e12.size(); j++) if (e12[j] == i) {
			D = dist12[j][e.u];
		}
		int G = min(A + B + e.c, E), H = min(C + D + e.c, F);
		if (G >= 1e9 || H >= 1e9) continue;
		ret = min(ret,G + H + e.d);
	}
	printf ("%d\n",ret > 15e8 ? -1 : ret);
    return 0;
}
//only O(N) "special" edges both ways, do dijkstra without each
//O(N^3) total

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

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

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