結果

問題 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,835 ms
コンパイル使用メモリ 173,980 KB
実行使用メモリ 31,408 KB
最終ジャッジ日時 2023-10-10 00:01:24
合計ジャッジ時間 19,871 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,704 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 381 ms
30,952 KB
testcase_03 AC 357 ms
28,088 KB
testcase_04 AC 456 ms
30,044 KB
testcase_05 AC 341 ms
31,064 KB
testcase_06 AC 433 ms
27,896 KB
testcase_07 AC 421 ms
29,184 KB
testcase_08 AC 286 ms
28,360 KB
testcase_09 AC 388 ms
26,568 KB
testcase_10 AC 290 ms
27,880 KB
testcase_11 AC 407 ms
28,580 KB
testcase_12 AC 396 ms
28,604 KB
testcase_13 AC 387 ms
31,144 KB
testcase_14 AC 337 ms
26,528 KB
testcase_15 AC 350 ms
27,640 KB
testcase_16 AC 422 ms
29,976 KB
testcase_17 AC 443 ms
31,408 KB
testcase_18 AC 396 ms
28,920 KB
testcase_19 AC 380 ms
28,136 KB
testcase_20 AC 419 ms
27,284 KB
testcase_21 AC 374 ms
30,520 KB
testcase_22 AC 396 ms
28,044 KB
testcase_23 AC 444 ms
31,404 KB
testcase_24 AC 371 ms
27,720 KB
testcase_25 AC 409 ms
29,988 KB
testcase_26 AC 375 ms
28,968 KB
testcase_27 AC 380 ms
28,840 KB
testcase_28 AC 350 ms
31,032 KB
testcase_29 AC 445 ms
29,388 KB
testcase_30 AC 511 ms
30,020 KB
testcase_31 AC 498 ms
29,388 KB
testcase_32 AC 2 ms
4,352 KB
testcase_33 AC 152 ms
24,900 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