結果

問題 No.134 走れ！サブロー君
ユーザー sntea
提出日時 2016-10-16 18:25:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,228 ms / 5,000 ms
コード長 5,811 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 196,080 KB
実行使用メモリ 189,484 KB
最終ジャッジ日時 2024-11-22 12:05:56
合計ジャッジ時間 5,809 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef LOCAL111
#else
    #define NDEBUG
#endif
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; 
    }
#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RBP(i,a) for(auto& i : a)
#ifdef LOCAL111
    #define DEBUG(x) cout<<#x<<": "<<(x)<<endl
    template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
    #define DEBUG(x) true
    template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
#define rangej(a,b,c) ((a) <= (c) and (c) < (b))
#define rrangej(b,c) rangej(0,b,c)
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
typedef pair<LL,LL> LP;
void ios_init(){
    cout.setf(ios::fixed);
    cout.precision(12);
#ifdef LOCAL111
    return;
#endif
    ios::sync_with_stdio(false); cin.tie(0);    
}
#define double long double
//library
typedef double cost_t;
class Edge {
public:
    int to;
    cost_t cost;
    
    Edge(){
    }
    Edge(int x,cost_t y){
        to = x;
        cost = y;
    }
    bool operator< (const Edge& x) const {
        if(cost != x.cost) return cost < x.cost;
        return to < x.to;
    }
    bool operator> (const Edge& x) const {
        if(cost != x.cost) return cost > x.cost;
        return to > x.to;
    }
};
class Graph {
private:
    //const long long int INF = (long long)1e18;
    vector<vector<Edge> > v; 
    int n;
public:
    Graph(int x){
        n = x;
        v = vector<vector<Edge> >(x);
    }
    vector<Edge>& operator[](int x){
        return v[x];
    }
    const vector<Edge>& operator[](int x) const {
        return v[x];
    }
    int size() const {
        return n;
    }
    void add_edge(int from, Edge e){
        v[from].push_back(e);
    }
    void add_edge(int from, int to, cost_t cost){
        add_edge(from,Edge(to,cost));
    }
    void add_uedge(int from, int to, cost_t cost){
        add_edge(from,to,cost);
        add_edge(to,from,cost);
    }
};
vector<cost_t> dijkstra(int from, const Graph& v)
{
    vector<cost_t> dist(v.size(),INF);
    priority_queue<Edge,vector<Edge>,greater<Edge>> que;
    que.push(Edge(from,0));
    while(!que.empty()){
        Edge e = que.top();
        que.pop();
        if(dist[e.to] == INF){
            dist[e.to] = e.cost;
            for(auto to : v[e.to]){
                if(dist[to.to] == INF)
                    que.push(Edge(to.to, e.cost+to.cost));
            }
        }
    }
    return dist;
}
vector<cost_t> bellmanford(int from, const Graph& g)
{
    vector<cost_t> res(g.size(),INF);
    res[from] = 0;
    bool conf = true;
    int cnt = 0;
    while(conf){
        conf = false;
        for(int i = 0; i < g.size(); i++){
            if(res[i] != INF)
            for(const auto& e : g[i]){
                if(res[e.to] > res[i]+e.cost){
                    conf = true;
                    res[e.to] = res[i]+e.cost;
                }
            }
        }
        if(cnt > g.size()+5) return vector<cost_t>();
        cnt++;
    }
    return res;
}
Graph prim(const Graph g)
{
    using T = tuple<cost_t, int, int>;
    priority_queue<T, vector<T>, greater<T>> qu;
    int n = g.size();
    assert(n != 0);
    vector<bool> added(n,false);
    qu.emplace(0,0,0);
    Graph res(n);
    while(!qu.empty()){
        int from, to;
        cost_t cost;
        tie(cost, from, to) = qu.top();
        qu.pop();
        if(!added[to]){
            added[to] = true;
            res.add_edge(from, to, cost);
            res.add_edge(to, from, cost);
            for(const auto &e : g[to]){
                if(!added[e.to]){
                    qu.emplace(e.cost, to, e.to);
                }
            }
        }
    }
    return res;
}
vector<int> tree_getorder(const Graph &g, int root)
{
    vector<int> res;
    function<void(int p, int pre)> func = [&](int p, int pre){
        for(auto &e : g[p]){
            if(e.to != pre){
                func(e.to,p);
            }
        }
        res.push_back(p);
    };
    func(root,-1);
    return res;
}
vector<int> tree_getpar(const Graph &g, int root)
{
    vector<int> par(g.size(),root);
    function<void(int p, int pre)> func = [&](int p, int pre){
        par[p] = pre;
        for(auto &e : g[p]){
            if(e.to != pre){
                func(e.to,p);
            }
        }
    };
    func(root,root);
    return par;
}
//未検証
vector<int> toposort(const Graph &g, int start)
{
    int n = g.size();
    vector<int> res;
    res.reserve(n);
    vector<bool> used(n,false);
    function<void(int)> rec = [&](int p){
        if(used[p]) return;
        used[p] = true;
        for(auto&& e : g[p]) {
            rec(e.to);
        }
        res.push_back(p);
    };
    rec(start);
    return res;
}
//liblary
int main()
{
    ios_init();
    int x0, y0;
    while(cin >> x0 >> y0){
        int n;
        cin >> n;
        using T = tuple<int,int,double>;
        vector<T> v(n);
        double sumw = 0;
        REP(i,n){
            int x,y;
            double w;
            cin >> x >> y >> w;
            sumw += w;
            v[i] = T(x,y,w);
        }
        Graph g((n)*(1<<n)+2);
        function<int(int,int)> mp = [&](int p, int mask) -> int{
            return p*(1<<n)+mask;
        };
        REP(i,n) REP(mask,1<<n){
            int x,y;
            double w;
            tie(x,y,w) = v[i];
            double sw = 0;
            REP(j,n){
                if(!((mask>>j)&1)){
                    sw += get<2>(v[j]);
                }
            }
            REP(j,n){
                int nx, ny;
                double nw;
                tie(nx,ny,nw) = v[j];
                int dis = abs(x-nx)+abs(y-ny);
                g.add_uedge(mp(i,mask),mp(j,mask|(1<<j)),dis*(sw+100.)/120);
            }
        }
        int sp = SZ(g)-2;
        int gp = SZ(g)-1;
        REP(i,n){
            int x,y;
            tie(x,y,ignore) = v[i];
            int dis = abs(x0-x)+abs(y-y0);
            g.add_uedge(sp,mp(i,1<<i),dis*(sumw+100.)/120);
            g.add_uedge(gp,mp(i,(1<<n)-1),dis*100./120);
        }
        auto ans = dijkstra(sp,g);
        DEBUG(sumw);
        cout << ans[gp]+sumw << endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0