제출 #575893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575893		benson1029	Robot (JOI21_ho_t4)	C++14	100 / 100	1473 ms	110620 KiB

Main

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

int n, m;
int a, b, c, p;
vector< pair<int, pair<int,long long> > > v[100005];
map< pair<int,int> , vector< pair< pair<int,int>, long long > > > edg;
int cnt[200005]; long long sum[200005];
priority_queue< pair<long long, pair<int,int> > > pq;
map< pair<int,int>, long long > dis;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		cin >> a >> b >> c >> p;
		v[a].push_back({b, {c, p} });
		v[b].push_back({a, {c, p} });
	}
	for(int i=1; i<=n; i++) {
		sort(v[i].begin(), v[i].end());
		for(auto j:v[i]) {
			cnt[j.second.first]++;
			sum[j.second.first] += j.second.second;
		}
		for(auto j:v[i]) {
			// case 1: direct
			if(cnt[j.second.first] == 1)
				edg[{i, 0}].push_back({{j.first, 0}, 0LL});
			else
				edg[{i, 0}].push_back({{j.first, 0}, j.second.second});
		}
		for(auto j:v[i]) {
			edg[{j.first, 0}].push_back({{i, j.second.first}, 0});
			edg[{i, j.second.first}].push_back({{j.first, 0}, sum[j.second.first]-j.second.second});
		}
		dis[{i, 0}] = 1e18;
		for(auto j:v[i]) {
			if(cnt[j.second.first] > 0) {
				edg[{i, 0}].push_back({{i, j.second.first}, 0});
				dis[{i, j.second.first}] = 1e18;
			}
			cnt[j.second.first] = sum[j.second.first] = 0;
		}
	}
	dis[{1, 0}] = 0;
	pq.push({0, {1, 0}});
	while(!pq.empty()) {
		auto curr = pq.top().second;
		if(dis[curr] != -pq.top().first) {
			pq.pop();
			continue;
		}
		pq.pop();
		if(curr == make_pair(n, 0)) {
			cout << dis[curr] << "\n";
			return 0;
		}
		for(auto j: edg[curr]) {
			if(dis[curr] + j.second < dis[j.first]) {
				dis[j.first] = dis[curr] + j.second;
				pq.push({-dis[j.first], j.first});
			}
		}
	}
	cout << "-1\n";
}

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