이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define bug(x) cout << #x << " : " << x << '\n'
#define bug2(x, y) cout << #x << ' ' << #y << " : " << x << ' ' << y << '\n'
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e2 + 10;
const int maxm = 5e4 + 10;
const int mod = 1e9 + 7;
const int inf = 2e9 + 10;
int n, m;
int u[maxn], v[maxn], c[maxn], f[maxn];
int d[2][2][maxn][maxn];
int par[2][2][maxn];
bool mark[maxn];
vector<int> G[maxn][2];
int ant(int e, int v){
return ::v[e] + ::u[e] - v;
}
void dijkstra(int src, bool st, bool eg, int s){
int (&d)[maxn] = ::d[st][eg][s];
int (&p)[maxn] = par[st][eg];
fill_n(d, maxn, inf);
memset(mark, 0, sizeof mark);
if(!s)
memset(p, -1, sizeof p);
d[src] = 0;
while(true){
int v = -1, h = inf;
for(int i = 1; i <= n; i ++)
if(!mark[i] and d[i] < h)
v = i, h = d[i];
if(v == -1) return;
mark[v] = true;
for(int e : G[v][eg]){
int u = ant(e, v);
int res = min((ll)h + c[e], (ll)inf);
if(res < d[u]){
d[u] = res;
if(!s)
p[u] = e;
}
}
}
}
int main(){
ios;
cin >> n >> m;
for(int i = 0; i < m; i ++){
int u, v, c, f;
cin >> u >> v >> c >> f;
G[u][0].pb(i);
G[v][1].pb(i);
::u[i] = u;
::v[i] = v;
::c[i] = c;
::f[i] = f;
}
for(int i = 0; i <= 1; i ++){
dijkstra(1, 0, i, 0);
dijkstra(n, 1, i, 0);
}
for(int i = 0; i <= 1; i ++){
for(int j = 0; j <= 1; j ++){
for(int v = 1; v <= n; v ++){
int e = par[i][j][v];
if(~e){
int x = c[e];
c[e] = inf;
dijkstra(i ? n : 1, i, j, v);
c[e] = x;
}
}
}
}
ll ans = (ll)d[0][0][0][n] + d[1][0][0][1];
for(int i = 0; i < m; i ++){
int u = ::u[i];
int v = ::v[i];
int c = ::c[i];
int f = ::f[i];
int state[2][2];
for(int j = 0; j <= 1; j ++){
state[j][0] = i == par[j][0][v] ? v : 0;
state[j][1] = i == par[j][1][u] ? u : 0;
}
int (&d1_out)[maxn] = d[0][0][state[0][0]];
int (&d1_in)[maxn] = d[0][1][state[0][1]];
int (&dn_out)[maxn] = d[1][0][state[1][0]];
int (&dn_in)[maxn] = d[1][1][state[1][1]];
ll res1 = min((ll)d1_out[n], (ll)d1_out[v] + c + dn_in[u]);
ll resn = min((ll)dn_out[1], (ll)dn_out[v] + c + d1_in[u]);
ans = min(ans, res1 + resn + f);
}
if(ans >= inf)
ans = -1;
cout << ans << '\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... |