結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | sak |
提出日時 | 2020-12-02 03:27:35 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,876 bytes |
コンパイル時間 | 3,793 ms |
コンパイル使用メモリ | 218,956 KB |
実行使用メモリ | 67,844 KB |
最終ジャッジ日時 | 2023-10-11 04:24:39 |
合計ジャッジ時間 | 19,470 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,356 KB |
testcase_02 | AC | 270 ms
61,708 KB |
testcase_03 | AC | 229 ms
55,084 KB |
testcase_04 | AC | 320 ms
57,356 KB |
testcase_05 | AC | 242 ms
61,580 KB |
testcase_06 | AC | 290 ms
53,932 KB |
testcase_07 | AC | 275 ms
57,644 KB |
testcase_08 | AC | 225 ms
55,696 KB |
testcase_09 | AC | 280 ms
50,768 KB |
testcase_10 | AC | 227 ms
54,992 KB |
testcase_11 | AC | 290 ms
55,976 KB |
testcase_12 | AC | 297 ms
55,244 KB |
testcase_13 | AC | 275 ms
62,240 KB |
testcase_14 | AC | 261 ms
51,300 KB |
testcase_15 | AC | 258 ms
53,636 KB |
testcase_16 | AC | 319 ms
57,344 KB |
testcase_17 | AC | 289 ms
61,672 KB |
testcase_18 | AC | 259 ms
56,676 KB |
testcase_19 | AC | 289 ms
53,772 KB |
testcase_20 | AC | 286 ms
51,700 KB |
testcase_21 | AC | 275 ms
60,060 KB |
testcase_22 | AC | 303 ms
52,844 KB |
testcase_23 | AC | 273 ms
62,056 KB |
testcase_24 | AC | 287 ms
52,980 KB |
testcase_25 | AC | 309 ms
57,824 KB |
testcase_26 | AC | 279 ms
56,184 KB |
testcase_27 | AC | 286 ms
56,012 KB |
testcase_28 | AC | 241 ms
60,784 KB |
testcase_29 | AC | 323 ms
55,904 KB |
testcase_30 | AC | 317 ms
58,056 KB |
testcase_31 | AC | 309 ms
56,848 KB |
testcase_32 | AC | 2 ms
4,356 KB |
testcase_33 | AC | 178 ms
48,256 KB |
testcase_34 | TLE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> p_ll; template<class T> void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; } #define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++) #define all(vec) vec.begin(), vec.end() #define rep(i,N) repr(i,0,N) #define per(i,N) for (int i=(int)N-1; i>=0; i--) const ll MOD = pow(10,9)+7; const ll LLINF = pow(2,61)-1; const int INF = pow(2,30)-1; vector<ll> fac; void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; } ll modpow(ll x, ll p) { ll result = 1, now = 1, pm = x; while (now<=p) { if (p&now) { result = result * pm % MOD; } now*=2; pm = pm*pm % MOD; } return result; } ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; } ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; } ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); } ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- struct MinCostFlow { struct edge { ll to, cap, cost, rev, idx; bool isrev; }; struct vertex { ll d, from, pos; }; vector<vector<edge>> adj; vector<ll> potential; vector<vertex> minlen; MinCostFlow(ll n) { adj.resize(n); potential.resize(n); } void add_edge(ll from, ll to, ll cap, ll cost, ll idx = -1) { adj[from].push_back({to, cap, cost, (ll)adj[to].size(), idx, false}); adj[to].push_back({from, 0, -1*cost, (ll)adj[from].size()-1, idx, true}); } ll dijkstra(ll from, ll to) { ll N = adj.size(); auto c = [](const p_ll &x, const p_ll &y){return x.second>y.second;}; priority_queue<p_ll, vector<p_ll>, decltype(c)> q(c); minlen.assign(N,{LLINF,-1,-1}); minlen[from] = {0,-1,-1}; q.push(make_pair(from,0)); while(q.size()) { p_ll now = q.top(); q.pop(); ll np = now.first, nd = now.second; if (nd>minlen[np].d) continue; for (auto x: adj[np]) { if (x.cap==0||minlen[x.to].d<=minlen[np].d+x.cost) continue; q.push(make_pair(x.to, minlen[np].d+x.cost)); minlen[x.to] = {minlen[np].d+x.cost, np, adj[x.to][x.rev].rev}; } } return minlen[to].d; } ll dfs(ll from, ll to, ll flow) { if (from==to) return flow; auto &e = adj[minlen[to].from][minlen[to].pos]; ll f = dfs(from, minlen[to].from, min(flow, e.cap)); e.cap -= f; adj[e.to][e.rev].cap += f; return f; } ll calc(ll from, ll to, ll cost) { while(true) { if (cost==0||dijkstra(from, to)==LLINF) { ll result = 0; rep(i,adj.size()) { for (auto &x: adj[i]) { if (!x.isrev) { edge rev = adj[x.to][x.rev]; result += rev.cap * x.cost; } } } return result; } cost -= dfs(from, to, cost); } return 0; } void output() { rep(i,adj.size()) { for (auto &x: adj[i]) { if (!x.isrev) { edge rev = adj[x.to][x.rev]; cout << x.idx << ":" << i << "->" << x.to << " " << rev.cap << "/" << x.cap+rev.cap << endl; } } } } }; // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- int main() { ll N, M; cin >> N >> M; ll u[M], v[M], c[M], d[M]; rep(i,M) { cin >> u[i] >> v[i] >> c[i] >> d[i]; u[i]--; v[i]--; } MinCostFlow mcf(N); rep(i,M) { mcf.add_edge(u[i],v[i],1,c[i]); mcf.add_edge(v[i],u[i],1,c[i]); mcf.add_edge(u[i],v[i],1,d[i]); mcf.add_edge(v[i],u[i],1,d[i]); } ll result = mcf.calc(0,N-1,2); cout << result << endl; return 0; }