제출 #1047501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047501		TAhmed33	Robot (JOI21_ho_t4)	C++98	100 / 100	797 ms	119280 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 25;
int n, m;
vector <array <int, 3>> adj[MAXN];
map <int, vector <array <int, 2>>> adj2[MAXN];
int dist[MAXN];
map <int, int> dist2[MAXN];
map <int, int> sum[MAXN];
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		adj[a].push_back({b, c, d});
		adj[b].push_back({a, c, d});
		adj2[a][c].push_back({b, d});
		adj2[b][c].push_back({a, d});
		sum[a][c] += d;
		sum[b][c] += d;
	}
	priority_queue <array <int, 3>, vector <array <int, 3>>, greater <>> pq;
	pq.push({0, 1, 0});
	for (int i = 2; i <= n; i++) {
		dist[i] = 1e18;
	}
	for (int i = 1; i <= n; i++) {
		for (auto j : adj[i]) {
			dist2[i][j[1]] = 1e18;
		}
	}
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k[2] == 0) {
			if (k[0] > dist[k[1]]) {
				continue;
			}
			for (auto j : adj[k[1]]) {
				if (dist[j[0]] > sum[k[1]][j[1]] - j[2] + k[0]) {
					dist[j[0]] = sum[k[1]][j[1]] - j[2] + k[0];
					pq.push({dist[j[0]], j[0], 0});
				}
				if (dist[j[0]] > j[2] + k[0]) {
					dist[j[0]] = j[2] + k[0];
					pq.push({dist[j[0]], j[0]});
				}
				if (dist2[j[0]][j[1]] > k[0]) {
					dist2[j[0]][j[1]] = k[0];
					pq.push({k[0], j[0], j[1]});	
				}
			}
		} else {
			if (k[0] > dist2[k[1]][k[2]]) {
				continue;
			}
			for (auto j : adj2[k[1]][k[2]]) {
				if (k[0] + sum[k[1]][k[2]] - j[1] < dist[j[0]]) {
					dist[j[0]] = k[0] + sum[k[1]][k[2]] - j[1];
					pq.push({dist[j[0]], j[0], 0});
				}
			}
		}
	}
	cout << (dist[n] >= (int)(1e18) ? -1 : dist[n]) << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
} 

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42