This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii array<int,3>
#define pi array<int,2>
signed main() {
int n,m;cin>>n>>m;
vector<vector<pii>> g(n);
for (int i=0;i<m;i++) {
int a,b,c,p;cin>>a>>b>>c>>p;a--;b--;
g[a].push_back({c, b, p});
g[b].push_back({c, a, p});
}
for (int i=0;i<n;i++) {
sort(g[i].begin(), g[i].end());
}
vector<vector<pi>> gg(n);
for (int i=0;i<n;i++) {
vector<vector<pii>> buckets;
for (auto x:g[i]) {
if (buckets.size() == 0) {
buckets.push_back({x});
}
else if (buckets.back().back()[0] == x[0]) {
buckets[buckets.size()-1].push_back(x);
}
else {
buckets.push_back({x});
}
}
for (auto &x:buckets) {
if (x.size() == 1) {
gg[i].push_back({x[0][1], 0});
}
else if (x.size() == 2) {
auto y1 = x[0], y2 = x[1];
int mn = min(y1[2], y2[2]);
gg[y1[1]].push_back({y2[1], y1[2]});
gg[y2[1]].push_back({y1[1], y2[2]});
}
if (x.size() != 1) {
for (auto &y:x) {
gg[i].push_back({y[1], y[2]});
}
}
}
}
vector<int> dis(n, 1e15);
priority_queue<pi> pq;
dis[0] = 0;
for (int i=0;i<n;i++) {
pq.push({-dis[i], i});
}
vector<bool> vis(n, false);
while (!pq.empty()) {
auto [cost, node]=pq.top();pq.pop();
if (vis[node])continue;
vis[node] = true;
for (auto [ne, we]:gg[node]) {
if (dis[ne] > dis[node] + we) {
dis[ne] = dis[node] + we;
pq.push({-dis[ne], ne});
}
}
}
if (dis.back() == (int)1e15) {
cout<<-1<<"\n";
return 0;
}
cout<<dis.back()<<"\n";
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:46:21: warning: unused variable 'mn' [-Wunused-variable]
46 | int mn = min(y1[2], y2[2]);
| ^~
Main.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | auto [cost, node]=pq.top();pq.pop();
| ^
Main.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for (auto [ne, we]:gg[node]) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |