이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = INT_MAX;
const int LNF = 1e18;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 210;
int n, m;
int from[MAX], to[MAX], c[MAX], d[MAX]; // information of edges
vi edge[MAX];
vi spe; // edges on shortest path s -> t
bool isspe[MAX];
int dis[MAX][MAX], dis2[MAX][MAX]; // dis2 : dis. without using edges in sp
int res[MAX]; // res[i] = optimal answer if we choose to reverse edge i
void Dijkstra(int s, int t){
int disDij[MAX];
bool vis[MAX];
int pv[MAX], pe[MAX]; // id. of previous vertex, edge
FOR(i, 1, n, 1){
disDij[i] = LNF + 1;
vis[i] = 0;
}
disDij[s] = 0;
FOR(owo, 1, n, 1){
int Min = LNF, u = 0;
FOR(i, 1, n, 1){
if(vis[i] == 0 and Min > disDij[i]){
Min = disDij[i];
u = i;
}
}
for(int e : edge[u]){
int v = to[e];
if(disDij[u] + c[e] < disDij[v]){
disDij[v] = disDij[u] + c[e];
pv[v] = u;
pe[v] = e;
}
}
vis[u] = 1;
/*
cerr<<"dis : ";
FOR(i, 1, n, 1){
if(disDij[i] > 100) cerr<<"- ";
else cerr<<disDij[i]<<" ";
}
cerr<<endl;
*/
}
// find shortest path s -> t
spe.clear();
FOR(i, 1, m, 1){
isspe[i] = 0;
}
int ptr = t;
while(ptr != s){
spe.pb(pe[ptr]);
isspe[pe[ptr]] = 1;
ptr = pv[ptr];
}
reverse(spe.begin(), spe.end());
assert(!spe.empty());
}
void FloydWarshall(){
// init. dis, dis2
FOR(i, 1, n, 1){
FOR(j, 1, n, 1){
dis[i][j] = dis2[i][j] = LNF;
}
dis[i][i] = dis2[i][i] = 0;
}
FOR(e, 1, m, 1){
int u = from[e], v = to[e];
dis[u][v] = min(dis[u][v], c[e]);
if(!isspe[e]) dis2[u][v] = min(dis2[u][v], c[e]);
}
FOR(k, 1, n, 1){
FOR(i, 1, n, 1){
FOR(j, 1, n, 1){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
dis2[i][j] = min(dis2[i][j], dis2[i][k] + dis2[k][j]);
}
}
}
}
void solve(int s, int t){
// (s, t) = (1, n) or (n, 1)
//cerr<<"solve "<<s<<" -> "<<t<<endl;
Dijkstra(s, t);
//cerr<<"Dij : ok"<<endl;
FloydWarshall();
//cerr<<"FW : ok"<<endl;
// e not on sp
FOR(e, 1, m, 1){
if(isspe[e]) continue;
int u = from[e], v = to[e];
res[e] += min(dis[s][t], dis[s][v] + c[e] + dis[u][t]);
}
// e on sp
int sz = szof(spe);
//
FOR(i, 0, sz-2, 1){
assert(to[spe[i]] == from[spe[i+1]]);
}
//
FOR(i, 0, sz-1, 1){
int e = spe[i];
int Min = LNF;
FOR(j, 0, i, 1){
FOR(k, i, sz-1, 1){
int u = from[spe[j]], v = to[spe[k]];
Min = min(Min, dis[s][u] + dis2[u][v] + dis[v][t]);
}
}
res[e] += Min;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
FOR(i, 1, m, 1){
cin>>from[i]>>to[i]>>c[i]>>d[i];
edge[from[i]].pb(i);
}
//cerr<<"in : ok"<<endl;
// build 2 extra edges to guarantee there is a path 1 -> n, n -> 1
from[m+1] = 1, from[m+2] = n;
to[m+1] = n, to[m+2] = 1;
c[m+1] = c[m+2] = LNF;
d[m+1] = d[m+2] = LNF;
edge[1].pb(m+1);
edge[n].pb(m+2);
m += 2;
solve(1, n);
/*
int tmp[MAX];
FOR(e, 1, m, 1){
if(res[e] < LNF) cerr<<res[e]<<" ";
else cerr<<"- ";
tmp[e] = res[e];
}
cerr<<endl;
*/
solve(n, 1);
/*
FOR(e, 1, m, 1){
if(res[e] < LNF) cerr<<res[e] - tmp[e]<<" ";
else cerr<<"- ";
}
cerr<<endl;
*/
// subtask 2
FOR(i, 1, m-2, 2){
if(res[i] < LNF) assert(res[i] == res[i+1]);
}
int RES = dis[1][n] + dis[n][1]; // don't flip edges
FOR(e, 1, m, 1){
res[e] += d[e];
RES = min(RES, res[e]); // flip e
}
if(RES < LNF) cout<<RES<<'\n';
else cout<<-1<<'\n';
/*
res[0] = dis[1][n] + dis[n][1];
FOR(e, 0, m, 1){
if(res[e] < LNF) cerr<<res[e]<<" ";
else cerr<<"- ";
}
cerr<<endl;
*/
return 0;
}
# | 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... |