oj.uz

Submission #371310

# Submission time Handle Problem Language Result Execution time Memory
371310 2021-02-26T12:53:56 Z cheissmart Robot (JOI21_ho_t4) C++14
0 / 100
 525 ms 28384 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
// #define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

void DBG() {
	cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}

#define debug(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)


const int INF = 1e9 + 7, N = 1e5 + 7;

V<array<int, 3>> G[N]; // (to, color, cost)
unordered_map<int, ll> csum[N];
unordered_map<int, ll> dist[N];

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, c, p;
		cin >> u >> v >> c >> p;
		G[u].PB({v, c, p});
		G[v].PB({u, c, p});
		csum[u][c] += p;
		csum[v][c] += p;
	}
	dist[1][0] = 0;
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(dist[1][0], MP(1, 0)));
	while(pq.size()) {
		auto p = pq.top(); pq.pop();
		int u = p.S.F, c = p.S.S;
		if(p.F > dist[u][c]) continue;
		for(auto e:G[u]) {
			int v = e[0], ec = e[1], cost = e[2];
			if(c < 0) {
				if(ec == -c) {
					if(dist[v].count(ec) == 0 || dist[u][c] + csum[u][ec] - cost < dist[v][ec]) {
						dist[v][ec] = dist[u][c] + csum[u][ec] - cost;
						pq.push(MP(dist[v][ec], MP(v, ec)));
					}
				}
				continue;
			}
			if(c != ec) {
				if(dist[v].count(ec) == 0 || dist[u][c] + csum[u][ec] - cost < dist[v][ec]) {
					dist[v][ec] = dist[u][c] + csum[u][ec] - cost;
					pq.push(MP(dist[v][ec], MP(v, ec)));
				}
			}
			if(dist[v].count(0) == 0 || dist[u][c] + cost < dist[v][0]) {
				dist[v][0] = dist[u][c] + cost;
				pq.push(MP(dist[v][0], MP(v, 0)));
			}
			if(dist[v].count(-ec) == 0 || dist[u][ec] < dist[v][-ec]) {
				dist[v][-ec] = dist[u][ec];
				pq.push(MP(dist[v][-ec], MP(v, -ec)));
			}
		}
	}
	ll ans = 1e18;
	for(auto p:dist[n])
		if(p.F >= 0)
			ans = min(ans, p.S);
	if(ans >= 1e18) ans = -1;
	cout << ans << '\n';


}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13676 KB Output is correct
2 Correct 10 ms 13676 KB Output is correct
3 Incorrect 11 ms 13676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 525 ms 28384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13676 KB Output is correct
2 Correct 10 ms 13676 KB Output is correct
3 Incorrect 11 ms 13676 KB Output isn't correct
4 Halted 0 ms 0 KB -