제출 #1109331

#제출 시각아이디문제언어결과실행 시간메모리
1109331nh0902Robot (JOI21_ho_t4)C++17
0 / 100
222 ms33336 KiB
#include <bits/stdc++.h> using namespace std; const int N = 110000; long long const inf = 1e16; int n, m; long long D[N]; bool vst[N]; vector<pair<int, long long>> g[N]; vector<pair<int, pair<int, long long>>> v[N]; struct cmp{ bool operator() (pair<long long, int> a, pair<long long, int> b) { return a.first > b.first; } }; struct cmp2{ bool operator() (pair<pair<long long, int>, int> a, pair<pair<long long, int>, int> b) { return a.first.first > b.first.first; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; int a, b, c; long long p; for (int i = 1; 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 ++) { map<int, long long> m; for (auto e : v[i]) { if (m.find(e.second.first) == m.end()) { m[e.second.first] = 0; } m[e.second.first] += e.second.second; } for (auto e : v[i]) { //cout << i << " " << e.first << " : " << m[e.second.first] - e.second.second << "\n"; g[i].push_back({e.first, min(e.second.second, m[e.second.first] - e.second.second)}); } } priority_queue<pair<long long, int>, vector<pair<long long, int>>, cmp> pq; for (int i = 1; i <= n; i ++) { D[i] = inf; } D[1] = 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, x] = pq.top(); pq.pop(); if (vst[x]) continue; vst[x] = true; for (auto e : g[x]) { if (D[e.first] > d + e.second) { D[e.first] = d + e.second; pq.push({D[e.first], e.first}); } } } if (D[n] == inf) { cout << -1; return 0; } cout << D[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...