Submission #1106334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106334		pubin06	Robot (JOI21_ho_t4)	C++14	100 / 100	502 ms	94748 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, long long>> adj[5 * MXn];
vector<tuple<int, int, long long>> huh[MXn];
long long tot[5 * MXn];
long long d[5 * MXn];
void Dijkstra(void) {
	fill(d + 1, d + 1 + n + 500000, oo);
	d[1] = 0;
	using T = pair<long long, int>;
	priority_queue<T, vector<T>, 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, w]: adj[u]) if (d[v] > d[u] + w) pq.emplace(d[v] = d[u] + w, v);
	}
}

int num;
map<int, int> mp[MXn];
int mapping(int u, int c) {
	if (!mp[u].count(c)) mp[u][c] = ++num;
	return mp[u][c];
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n >> m;
    num = n;
    for (int i = 1, a, b, c, p; i <= m; i++) {
    	cin >> a >> b >> c >> p;
    	adj[a].emplace_back(b, p);
    	adj[b].emplace_back(a, p);
    	adj[a].emplace_back(mapping(a, c), 0);
    	adj[b].emplace_back(mapping(b, c), 0);
    	adj[a].emplace_back(mapping(b, c), 0);
    	adj[b].emplace_back(mapping(a, c), 0);
    	adj[mapping(b, c)].emplace_back(a, -p);
    	adj[mapping(a, c)].emplace_back(b, -p);
    	tot[mapping(a, c)] += p;
    	tot[mapping(b, c)] += p;
    }
    for (int i = n + 1; i <= num; i++) {
    	for (auto &[v, c]: adj[i]) {
    		c += tot[i];
    	}
    }
    Dijkstra();
    cout << (d[n] == oo ? -1 : d[n]);
    
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void Dijkstra()':
Main.cpp:27:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |   for (auto [v, w]: adj[u]) if (d[v] > d[u] + w) pq.emplace(d[v] = d[u] + w, v);
      |             ^
Main.cpp: In function 'int main()':
Main.cpp:57:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |      for (auto &[v, c]: adj[i]) {
      |                 ^

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