Submission #1105591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105591		pubin06	Robot (JOI21_ho_t4)	C++17	34 / 100	3064 ms	91232 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;
 
const int MXn = 100005;
const long long oo = 1e18;
const int MOD = 1e9 + 7;
 
int n, m;
vector<pair<int, pair<int, int>>> adj[MXn];
map<int, long long> tot[MXn];
map<int, pair<int, long long>> cost[MXn];
map<int, long long> d[MXn];
long long ans = oo;
void Dijkstra(void) {
	d[1][-1] = 0;
	priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<>> pq;
	pq.push({0, {1, -1}});
	while (sz(pq)) {
		int u = pq.top().se.fi, last = pq.top().se.se, di = pq.top().fi;
		pq.pop();
		if (u == n) ans = min(ans, di);
		if (d[u][last] != di) continue;
		// cerr << u << ' ' << last << ' ' << d[u][last] << '\n';
		for (auto V: adj[u]) {
			int v = V.fi, c = V.se.fi, p = V.se.se;
			if (last < 0) {
				if (!d[v].count(-1) || d[v][-1] > d[u][-1] + tot[u][c] - p) {
					d[v][-1] = d[u][-1] + tot[u][c] - p;
					pq.push({d[v][-1], {v, -1}});
				}
			} else {
				int lastc = cost[u][last].fi;
				if (lastc != c) {
					if (!d[v].count(-1) || d[v][-1] > d[u][last] + tot[u][c] - p) {
						d[v][-1] = d[u][last] + tot[u][c] - p;
						pq.push({d[v][-1], {v, -1}});
					}
				} else {
					if (!d[v].count(-1) || d[v][-1] > d[u][last] + tot[u][c] - p - cost[u][last].se) {
						d[v][-1] = d[u][last] + tot[u][c] - p - cost[u][last].se;
						pq.push({d[v][-1], {v, -1}});
					}
				}
			}
			if (!d[v].count(u) || d[v][u] > d[u][last] + p) {
				d[v][u] = d[u][last] + p;
				pq.push({d[v][u], {v, u}});
			}
		}
	}
}
 
signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1, a, b, c, p; i <= m; i++) {
    	cin >> a >> b >> c >> p;
    	adj[a].push_back({b, {c, p}});
    	adj[b].push_back({a, {c, p}});
    	if (!tot[a].count(c)) tot[a][c] = 0;
    	tot[a][c] += p;
    	if (!tot[b].count(c)) tot[b][c] = 0;
    	tot[b][c] += p;
    	cost[a][b] = cost[b][a] = {c, p};
    }
    Dijkstra();
    cout << (ans == oo ? -1 : ans);
    
    return 0;
}

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