#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> elist;
elist.push_back({0, 0, 0, 0});
for (int i = 0; i < m; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
elist.push_back({a, b, c, d});
}
int minans = INT_MAX;
for (int i = 0; i <= m; i++) {
vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
int curp = elist[i][3];
swap(elist[i][0], elist[i][1]);
// cout << "ELIST\n";
// for (auto a : elist) {
// for (auto b : a) cout << b << " ";
// cout << "\n";
// }
for (int j = 0; j <= m; j++) {
adj[elist[j][0]].emplace_back(elist[j][1], elist[j][2]);
}
vector<int> visited(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pqpii;
pqpii.emplace(0, 0);
while (!pqpii.empty()) {
pair<int, int> cur = pqpii.top();
pqpii.pop();
if (visited[cur.second] != INT_MAX) continue;
visited[cur.second] = cur.first;
for (auto a : adj[cur.second])
pqpii.emplace(a.second + cur.first, a.first);
}
curp += visited[n - 1];
// cout<<curp<<"\n";
pqpii.emplace(0, n - 1);
visited = vector<int>(n, INT_MAX);
while (!pqpii.empty()) {
pair<int, int> cur = pqpii.top();
pqpii.pop();
// cout<<cur.first<<" "<<cur.second<<"\n";
if (visited[cur.second] != INT_MAX) continue;
visited[cur.second] = cur.first;
for (auto a : adj[cur.second])
pqpii.emplace(a.second + cur.first, a.first);
}
curp += visited[0];
// cout<<curp<<"\n";
minans = min(minans, curp);
swap(elist[i][0], elist[i][1]);
}
if (minans == INT_MAX)
cout << "-1\n";
else
cout << minans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |