#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
typedef pair<int, int> pii;
#define MAXN 200
#define MAXM 50000
struct Edge {
int u, v, c, d;
};
int n, m;
Edge edges[MAXM];
list<int> adj[MAXN];
int dist[MAXN][MAXN];
int dis[MAXN];
int cost(int s, int t, int ri){
fill(dis, dis+n, INF);
priority_queue<pii> pq;
pq.push({0, s});
dis[s] = 0;
while (!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if (dis[u] != d) continue;
if (ri != -1 && edges[ri].v == u){
int v = edges[ri].u, cd = edges[ri].c;
if (d + cd < dis[v]){
dis[v] = d + cd;
pq.push({dis[v], v});
}
}
for (int i : adj[u]){
if (i == ri) continue;
int v = edges[i].v, cd = edges[i].c;
if (d + cd < dis[v]){
dis[v] = d + cd;
pq.push({dis[v], v});
}
}
}
return dis[t];
}
int cost(int ri = -1){ return cost(0, n-1, ri) + cost(n-1, 0, ri); }
int32_t main(){
//freopen("sol.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
dist[i][j] = INF;
dist[i][i] = 0;
}
for (int i = 0; i < m; i++){
auto &[u, v, c, d] = edges[i];
cin >> u >> v >> c >> d;
u--, v--;
adj[u].push_back(i);
dist[u][v] = min(dist[u][v], c);
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
int ans = cost();
for (int i = 0; i < m; i++){
auto [u, v, c, d] = edges[i];
int fw = min(dist[0][n-1], dist[0][v] + c + dist[u][n-1]),
bw = min(dist[n-1][0], dist[n-1][v] + c + dist[u][0]);
if (fw < INF && bw < INF && (fw + bw + d) < ans)
ans = min(ans, cost(i) + d);
}
cout << (ans >= INF ? -1 : ans) << '\n';
return 0;
}
Compilation message
ho_t4.cpp:50:2: error: extended character is not valid in an identifier
50 | //freopen("sol.in", "r", stdin);
| ^
ho_t4.cpp:50:5: error: extended character is not valid in an identifier
50 | //freopen("sol.in", "r", stdin);
| ^
ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:50:2: error: '\U000000a0' was not declared in this scope
50 | //freopen("sol.in", "r", stdin);
| ^
