#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 205, mxm = 50005;
struct ch{
int u, type; ll dd;
};
struct E{
int u, v, c, e;
};
int n, m;
vt<E>adj[mxn + 1], rev[mxn + 1];
E edge[mxm + 1];
bool used1[mxm + 1], vis[mxn + 1], usedn[mxn + 1];
pii trace[mxn + 1];
ll d[mxn + 1], d2[mxn + 1][2];
ll U = -1, V, W, ID = -1;
struct cmp{
bool operator()(const ch &a, const ch &b){
return(a.dd > b.dd);
}
};
void D(int s){
forr(i, 1, n + 1){
d[i] = 1e18; vis[i] = false;
trace[s] = make_pair(-1, -1);
}
d[s] = 0;
for(int i = 0; i < n; i++){
int u = -1; ll mn = 1e18;
for(int j = 1; j <= n; j++){
if(d[j] < mn && !vis[j]){
u = j;
}
}
vis[u] = true;
for(auto [v, c, e, id]: adj[u]){
if(id == ID)continue;
if(d[v] > d[u] + c){
d[v] = d[u] + c; trace[v] = make_pair(id, u);
}
}
if(u == U){
if(d[V] > d[u] + W){
d[V] = d[u] + W;
}
}
}
}
void D2(int s){
forr(i, 1, n + 1){
d2[i][0] = d2[i][1] = 1e18; vis[i] = false;
}
priority_queue<ch, vt<ch>, cmp>pq; d2[s][0] = 0; pq.push({s, 0, d2[s][0]});
while(!pq.empty()){
auto [u, type, dd] = pq.top(); pq.pop();
if(d2[u][type] != dd)continue;
for(auto [v, c, e, id]: adj[u]){
if(d2[v][type] > d2[u][type] + c){
d2[v][type] = d2[u][type] + c;
pq.push({v, type, d2[v][type]});
}
}
if(type == 0){
for(auto [v, c, e, id]: rev[u]){
if((s == 1 && usedn[id]) || (s == n && used1[id]))continue;
if(d2[v][1] > d2[u][0] + c + e){
d2[v][1] = d2[u][0] + c + e;
pq.push({v, 1, d2[v][1]});
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
forr(i, 0, m){
int u, v, c, e; cin >> u >> v >> c >> e;
adj[u].pb({v, c, e, i}); rev[v].pb({u, c, e, i});
edge[i] = {u, v, c, e};
}
bool ok1 = true, ok2 = true;
D(1);
ll dn = 1e18, d1 = 1e18;
if(d[n] < 1e18){
ok1 = false;
dn = d[n];
int v = n;
while(v != 1){
used1[trace[v].fi] = 1;
v = trace[v].se;
}
}
D(n);
if(d[1] < 1e18){
d1 = d[1];
ok2 = false;
int v = 1;
while(v != 1){
usedn[trace[v].fi] = 1;
v = trace[v].se;
}
}
//all edge from dijkstra Path -> o(n) Path
ll ans = d1 + dn;
if(ok1 && ok2){
cout << -1; return(0);
}
if(!ok1){
D2(n);
cout << d2[1][1];
ans = min(ans, d2[1][1] + dn);
}if(!ok2){
D2(1);
ans = min(ans, d2[n][1] + d1);
}
forr(i, 0, m){
if(used1[i] || usedn[i]){
ll curr = 0;
U = edge[i].v; V = edge[i].u; W = edge[i].c + edge[i].e; ID = i;
D(1); curr += d[n];
D(n); curr += d[1];
ans = min(ans, curr + edge[i].e);
}
}
if(ans >= 1e18){
cout << -1;
}else{
cout << ans;
}
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
3804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
