結果

問題 No.1301 Strange Graph Shortest Path
ユーザー kappybarkappybar
提出日時 2020-11-28 14:44:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,736 bytes
コンパイル時間 1,907 ms
コンパイル使用メモリ 177,452 KB
実行使用メモリ 39,260 KB
最終ジャッジ日時 2024-09-12 22:28:42
合計ジャッジ時間 19,445 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 357 ms
31,104 KB
testcase_03 AC 331 ms
28,288 KB
testcase_04 AC 444 ms
30,336 KB
testcase_05 AC 321 ms
31,232 KB
testcase_06 AC 424 ms
28,032 KB
testcase_07 AC 411 ms
29,440 KB
testcase_08 AC 286 ms
28,544 KB
testcase_09 AC 387 ms
26,752 KB
testcase_10 AC 292 ms
28,160 KB
testcase_11 AC 391 ms
29,056 KB
testcase_12 AC 388 ms
28,928 KB
testcase_13 AC 387 ms
31,232 KB
testcase_14 AC 341 ms
26,752 KB
testcase_15 AC 352 ms
27,776 KB
testcase_16 AC 411 ms
30,080 KB
testcase_17 AC 423 ms
31,360 KB
testcase_18 AC 377 ms
29,056 KB
testcase_19 AC 366 ms
28,288 KB
testcase_20 AC 402 ms
27,648 KB
testcase_21 AC 354 ms
30,464 KB
testcase_22 AC 377 ms
28,160 KB
testcase_23 AC 432 ms
31,488 KB
testcase_24 AC 369 ms
27,904 KB
testcase_25 AC 393 ms
30,208 KB
testcase_26 AC 349 ms
29,184 KB
testcase_27 AC 375 ms
29,056 KB
testcase_28 AC 360 ms
31,104 KB
testcase_29 AC 458 ms
29,824 KB
testcase_30 AC 480 ms
30,080 KB
testcase_31 AC 451 ms
29,696 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 160 ms
25,088 KB
testcase_34 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define chmin(x,y) x = min((x),(y));
#define chmax(x,y) x = max((x),(y));
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
const int INF = 1e9;
const long long LINF = 1e17;
const int MOD = 1000000007;
//const int MOD = 998244353;
const double PI = 3.14159265358979323846;

// Cap int ,Cost long long
template<typename Cap,typename Cost>
struct mcf_graph{
    struct edge{
        int to;
        Cap cap;
        Cost cost;
        int rev;
    };
    int n;
    vector<vector<edge>> G;
    vector<Cost> dist;
    vector<int> prev_edge;
    vector<int> prev_vertex;

    mcf_graph(int n):n(n),G(n),dist(n,-1),prev_edge(n),prev_vertex(n){}

    void add_edge(int from,int to,Cap cap,Cost cost){
        G[from].push_back(edge{to,cap,cost,(int)G[to].size()});
        G[to].push_back(edge{from,0,-cost,(int)G[from].size()-1});
    }

    // min cost  s -> t (f flow)
    pair<Cap,Cost> min_cost_max_flow(int s,int t,Cap f){
        Cost res = 0;
        Cap f_ = f;
        while(f > 0){
            fill(dist.begin(),dist.end(),LINF);
            dist[s] = 0;
            bool update = true;
            while(update){
                update = false;
                for(int i=0;i<n;i++){
                    if(dist[i]>=LINF) continue;
                    for(int j=0;j<(int)G[i].size();j++){
                        edge &e = G[i][j];
                        if(e.cap > 0 && dist[e.to] > dist[i] + e.cost){
                            dist[e.to] = dist[i] + e.cost;
                            prev_vertex[e.to] = i;
                            prev_edge[e.to] = j;
                            update = true;
                        }
                    }
                }
            }

            if(dist[t] == LINF){
                return pair<Cap,Cost>{f_-f,res};
            }

            Cap d = f;
            for(int v=t;v!=s;v=prev_vertex[v]){
                d = min(d,G[prev_vertex[v]][prev_edge[v]].cap);
            }
            f -= d;
            res += d*dist[t];
            for(int v=t;v!=s;v=prev_vertex[v]){
                edge &e = G[prev_vertex[v]][prev_edge[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return pair<Cap,Cost>{f_,res};
    }

};

int main(){
    int n,m;
    cin >> n >> m;
    mcf_graph<int,ll> G(n);
    rep(i,m){
        int u,v,c,d;
        cin >> u >> v >> c >> d;
        --u;--v;
        G.add_edge(u,v,1,c);
        G.add_edge(u,v,1,d);
        G.add_edge(v,u,1,c);
        G.add_edge(v,u,1,d);
    }
    auto ans =  G.min_cost_max_flow(0,n-1,2);
    cout << ans.second << endl;
    return 0;
}
0