Submission #1104975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104975		pubin06	Robot (JOI21_ho_t4)	C++14	0 / 100	291 ms	42036 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];
long long d[MXn];
void Dijkstra(void) {
	for (int i = 1; i <= n; i++) d[i] = oo;
	d[1] = 0;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
	pq.emplace(0, 1);
	while (sz(pq)) {
		int u = pq.top().se, di = pq.top().fi;
		pq.pop();
		if (d[u] != di) continue;
		for (auto V: adj[u]) {
			int v = V.fi, c = V.se.fi, p = V.se.se;
			if (d[v] > d[u] + min(tot[u][c] - p, p)) {
				d[v] = d[u] + min(tot[u][c] - p, p);
				pq.emplace(d[v], v);
			}
		}
	}
}

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;
    }
    Dijkstra();
    if (d[n] == oo) d[n] = -1;
    cout << d[n];
    
    return 0;
}

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