結果

問題 No.1301 Strange Graph Shortest Path
ユーザー kappybar
提出日時 2020-11-28 14:44:10
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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