#40394 (C++11) No.1 道のショートカット

提出ソース
結果

問題	No.1 道のショートカット
ユーザー	wahr69
提出日時	2015-07-31 14:29:20
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	24,368 bytes
コンパイル時間	1,768 ms
コンパイル使用メモリ	118,396 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-08 04:10:04
合計ジャッジ時間	3,042 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	WA	-
testcase_15	AC	2 ms 5,376 KB
testcase_16	WA	-
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	WA	-
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	WA	-
testcase_33	AC	2 ms 5,376 KB
testcase_34	WA	-
testcase_35	AC	2 ms 5,376 KB
testcase_36	WA	-
testcase_37	AC	3 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>

#include <array>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#include <string>
#include <sstream>

#include <memory>
#include <cassert>

#include <functional>

#define SAFE_DELETE(p)       { delete (p);     (p) = nullptr; }
#define SAFE_DELETE_ARRAY(p) { delete[] (p);   (p) = nullptr; }

using namespace std;

int C;

namespace ValLib {

    const int MOD = 1000000007;

    typedef unsigned long long ull;
    
    template <typename Key, typename Value>
    class unordered_vmap;
    template <typename T>
    using sptr = typename std::shared_ptr<T>;
    class vnode;
    class vegde;
    class vgraph;
    class SearchResult;

    template<typename T>
    void fill(vector<vector<T>>& vec, const T& value) {
        for (vector<T>& t : vec) {
            fill(t, value);
        }
    }

    template<typename T>
    void fill(vector<T>& vec, const T& value) {
        fill(vec.begin(), vec.end(), value);
    }

    template<typename T>
    void resize(vector<vector<T>>& vec, int size1, int size2) {
        vec.resize(size1);
        for (vector<T>& t : vec) {
            t.resize(size2);
        }
    }

    template<typename Key, typename Value>
    class umap : public std::unordered_map<Key, Value> {
    public:
        bool containsKey(const Key& key) const;
        bool containsValue(const Value& val) const;
    };

    template<typename Key, typename Value>
    bool umap<Key, Value>::containsKey(const Key& key) const {
        return (this->find(key) != this->end());
    }

    template<typename Key, typename Value>
    bool umap<Key, Value>::containsValue(const Value& val) const {
        for(auto itr = this->begin(); itr != this->end(); ++itr) {
            if (itr->second == val) {
                return true;
            }
        }
        return false;
    }

    class Point {
    public:

        inline Point() :
        x(-1),
        y(-1)
        {}

        inline Point(int _x, int _y) :
        x(_x),
        y(_y)
        {}

        int x;
        int y;
    };

    /// <summary>
    /// 素集合データ構造
    /// </summary>
    class UnionFind {
    public:
 
        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="N">要素数</param>
        UnionFind(int N) {
           parent.resize(N);
           for (int i = 0; i < N; ++i) {
              parent[i] = i;
           }
        }
 
        /// <summary>
        /// 要素xの根を探索
        /// </summary>
        /// <param name="x">探索する要素番号(0～N-1)</param>
        /// <returns>要素xの根(0～N-1)</returns>
        int find(int x) {
           if (parent[x] == x) {
              return x;
           } else {
              parent[x] = find(parent[x]); // 経路圧縮(間接的な要素をrootに直接つなぐ)
              return parent[x];
           }
        }
 
        /// <summary>
        /// ２つの要素の根が同じか
        /// </summary>
        /// <param name="x1">探索する要素番号１(0～N-1)</param>
        /// <param name="x2">探索する要素番号２(0～N-1)</param>
        /// <returns>true: 同じ根, false: 異なる根</returns>
        bool same(int x1, int x2) {
           return find(x1) == find(x2);
        }
 
        /// <summary>
        /// ２つの要素の根同士を繋ぐ
        /// </summary>
        /// <param name="x1">要素番号１(0～N-1)</param>
        /// <param name="x2">要素番号１(0～N-1)</param>
        void union_elements(int x1, int x2) {
           int rootX1 = find(x1);
           int rootX2 = find(x2);
           parent[rootX2] = rootX1;
        }

    private:
         vector<int> parent;

    };

    class vmath {
    public:

        // 約数を全て求める O(√n)
        static ull calcDivisors(list<ull>* divisors, ull n) {
            divisors->clear();
            if (n <= 0ull) {
                return 0ull;
            }
            divisors->push_back(1ull);
            if (n != 1ull) {
                divisors->push_back(n);
            }
            for (ull i = 2ull; i * i <= n; ++i) {
                if (n % i == 0ull) {
                    divisors->push_back(i);
                    divisors->push_back(n / i);
                }
            }
            return divisors->size();
        }

        // 約数の個数を返す O(√n)
        static ull calcDivisorNum(ull n) {
            if (n <= 0ull) {
                return 0ull;
            }
            ull count = 1ull; // for 1
            if (n != 1ull) {
                ++count; // for n
            }
            // for 2～n-1
            for (ull i = 2ull; i * i <= n; ++i) {
                if (n % i == 0ull) {
                    count += 2ull;
                }
            }
            return count;
        }

        // 素因数分解 O(√n)
        static int decompositPrime(list<ull>* primes, ull n) {
            primes->clear();
            if (n == 0) {
                return 0ull;
            }
            if (n == 1) {
                primes->push_back(1);
                return 1ull;
            }
            // 割る数の初期値
            ull a = 2ull;
            // √n ≧ a ( n ≧ a * a ) の間ループ処理
            while (n >= a * a) {
                if (n % a == 0ull) {
                    // a で割り切れたら、a は素因数
                    primes->push_back(a);
                    // そして、割られる数を a で割る
                    n /= a;
                } else {
                    // a で割り切れなかったら、 a を 1 増加させる
                    a++;
                }
            }
            primes->push_back(n);
            return primes->size();
        }

        // 素因数の数を返す O(√n)
        static ull calcPrimeNum(ull n) {
            if (n <= 1) {
                return n;
            }
            ull count = 0ull;
            // 割る数の初期値
            ull a = 2ull;
            // √n ≧ a ( n ≧ a * a ) の間ループ処理
            while (n >= a * a) {
                if (n % a == 0ull) {
                    // a で割り切れたら、a は素因数
                    ++count;
                    // そして、割られる数を a で割る
                    n /= a;
                } else {
                    // a で割り切れなかったら、 a を 1 増加させる
                    a++;
                }
            }
            ++count; // for n
            return count;
        }

        // 階乗
        static ull fact(ull x) {
            if (x == 0ull) {
                return 1ull;
            } else {
                return x * fact(x - 1ull);
            }
        }

        // 順列 nPr
        static ull permutation(int n, int r) {
            assert(n >= r);
            //return fact(n) / fact(n - r);
            ull result = 1;
            for (ull i = n; i > n - r; --i) {
                result *= i;
            }
            return result;
        }

        // 組み合わせ nCr
        // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある
        static ull combination(int n, int r) {
            assert(n >= r);
            assert(n <= mPascalTriangleDepth);
            return mPascalTriangle[n][r];
        }

        // 重複組合せ nHr = n+r-1Cr
        // 使いどころ：n人にr個を配るとき、同じ人に何個配っても良い場合とか
        // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。
        // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1
        // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr
        static ull repeatedCombination(int n, int r) {
            return combination(n + r - 1, r);
        }

        // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。
        static void makePascalTriangle(int depth) {
            resize(mPascalTriangle, depth + 1, depth + 1);
            for (int i = 0; i <= depth; ++i) {
                mPascalTriangle[i][0] = 1;
                for (int j = 1; j <= i; ++j) {
                    mPascalTriangle[i][j] = mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1];
                }
            }
            mPascalTriangleDepth = depth;
        }

        // xのN桁目の数値を得る
        static ull getNDigitNumber(ull x, ull n) {
            return (x / pow(10ull, n - 1ull)) % 10;
        }

        // xのN桁目の数値を得る
        static int getNDigitNumber(int x, int n) {
            assert(n <= 10);
            return (x / pow(10, n - 1)) % 10;
        }

        // xのN乗を求める(バイナリ法) O(logN)
        static ull pow(ull x, ull n) {
            assert(x >= 0ull);
            assert(n >= 0ull);
            if (x == 0ull) {
                if (n == 0ull) {
                    return 1ull;
                } else {
                    return 0ull;
                }
            }
            ull result = 1ull;
            ull z = x;
            while (n > 0ull) {
                if (n & 1ull) {
                    result *= z;
                }
                z *= z;
                n >>= 1;
            }
            return result;
        }

        // xのN乗を求める(バイナリ法) O(logN)
        static int pow(int x, int n) {
            assert(x >= 0);
            assert(n >= 0);
            if (x == 0) {
                if (n == 0) {
                    return 1;
                } else {
                    return 0;
                }
            }
            int result = 1;
            int z = x;
            while (n > 0) {
                if (n & 1) {
                    result *= z;
                }
                z *= z;
                n >>= 1;
            }
            return result;
        }

    private:
        static int mPascalTriangleDepth;
        static vector<vector<ull>> mPascalTriangle;
    };
    int vmath::mPascalTriangleDepth = 0;
    vector<vector<ull>> vmath::mPascalTriangle;

    class vmath_mod {
    public:

        // 階乗
        static ull fact(ull x) {
            ull result = 1ull;
            for (ull i = 1ull; i <= x; ++i) {
                result *= i;
                result %= MOD;
            }
            return result;
        }

        // 順列 nPr
        static ull permutation(int n, int r) {
            assert(n >= r);
            //return fact(n) / fact(n - r);
            ull result = 1;
            for (ull i = n; i > n - r; --i) {
                result *= i;
                result %= MOD;
            }
            return result;
        }

        // 組み合わせ nCr
        // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある
        static ull combination(int n, int r) {
            assert(n >= r);
            assert(n <= mPascalTriangleDepth);
            return mPascalTriangle[n][r];
        }

        // 重複組合せ nHr = n+r-1Cr
        // 使いどころ：n人にr個を配るとき、同じ人に何個配っても良い場合とか
        // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。
        // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1
        // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr
        static ull repeatedCombination(int n, int r) {
            return combination(n + r - 1, r);
        }

        // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。
        static void makePascalTriangle(int depth) {
            resize(mPascalTriangle, depth + 1, depth + 1);
            for (int i = 0; i <= depth; ++i) {
                mPascalTriangle[i][0] = 1;
                for (int j = 1; j <= i; ++j) {
                    mPascalTriangle[i][j] = (mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]) % MOD;
                }
            }
            mPascalTriangleDepth = depth;
        }

        // xのN桁目の数値を得る
        static ull getNDigitNumber(ull x, ull n) {
            return (x / pow(10ull, n - 1ull)) % 10;
        }

        // xのN桁目の数値を得る
        static int getNDigitNumber(int x, int n) {
            assert(n <= 10);
            return (x / pow(10, n - 1)) % 10;
        }

        // xのN乗を求める O(n)
        static ull pow(ull x, ull n) {
            if (x == 0ull) {
                if (n == 0ull) {
                    return 1ull;
                } else {
                    return 0ull;
                }
            }
            ull result = 1ull;
            for (ull i = 0ull; i < n; ++i) {
                result *= x;
                result %= MOD;
            }
            return result;
        }

        // xのN乗を求める O(n)
        static int pow(int x, int n) {
            assert(x >= 0);
            assert(n >= 0);
            if (x == 0) {
                if (n == 0) {
                    return 1;
                } else {
                    return 0;
                }
            }
            int result = 1;
            for (int i = 0; i < n; ++i) {
                result *= x;
                result %= MOD;
            }
            return result;
        }

    private:
        static int mPascalTriangleDepth;
        static vector<vector<ull>> mPascalTriangle;
    };
    int vmath_mod::mPascalTriangleDepth = 0;
    vector<vector<ull>> vmath_mod::mPascalTriangle;

    class vegde {
    public:
        vegde() :
        mLeft(nullptr),
        mRight(nullptr) {

        }

        vegde(sptr<vnode> left, sptr<vnode> right) :
        vegde() {
            mLeft = left;
            mRight = right;
        }

        vegde(sptr<vnode> left, sptr<vnode> right, int cost, int yen) :
        vegde(left, right) {
            mCost = cost;
			mMoney = yen;
        }

        sptr<vnode> getOpponent(sptr<vnode> node) const {
            assert(node == mLeft || node == mRight);
            return (node == mLeft) ? mLeft : (node == mRight) ? mRight : nullptr;
        }
        
        void set(sptr<vnode> left, sptr<vnode> right) { mLeft = left; mRight = right; }

        const sptr<vnode>& getLeft() const { return mLeft; }
        const sptr<vnode>& getRight() const { return mRight; }
        int getCost() const { return mCost; }
        int getMoney() const { return mMoney; }
    private:
        sptr<vnode> mLeft;
        sptr<vnode> mRight;
        int mCost;
		int mMoney;
    };

    class vnode {
    public:
        vnode() :
        mID(-1) {

        }

        vnode(int id) :
        vnode() {
            mID = id;
        }

        void addEgde(sptr<vegde> egde) {
            mEgdeList.push_back(egde);
        }
        void removeEgde(int nodeID1, int nodeID2) {
            auto itrNewEnd = std::remove_if(mEgdeList.begin(), mEgdeList.end(), [=](sptr<vegde> e)->bool {
                return (e->getLeft()->getID() == nodeID1 && e->getRight()->getID() == nodeID2);
            });
            mEgdeList.erase(itrNewEnd, mEgdeList.end());
        }

        int getID() const { return mID; }
        const list<sptr<vegde>>& getEgde() const { return mEgdeList; }
    private:
        list<sptr<vegde>> mEgdeList;
        int mID;
    };

    // グラフ
    class vgraph {
    public:

        const int INF = 1000000;

        vgraph(int nodeNum) {
            mNodeNum = nodeNum;
            mNodes.resize(nodeNum);
            for (int i = 0; i < nodeNum; ++i) {
                mNodes[i] = make_shared<vnode>(i);
            }
            mMinimumDists.resize(mNodeNum);
            mPrevNodes.resize(mNodeNum);
        }

        void addEgde(int nodeID1, int nodeID2) {
            addEgde(nodeID1, nodeID2, 1, 1);
        }

        virtual void addEgde(int nodeID1, int nodeID2, int cost, int time) = 0;
        virtual void removeEgde(int nodeID1, int nodeID2) = 0;

        // ベルマンフォード法を使ってある頂点から全ての頂点への最短距離を求める
        // startからたどり着ける場所に負のループが存在する場合はfalseを返す
        // ダイクストラ法と違い、負のコストの辺があっても最短距離を計算できる
        // O(V*E)
        bool bellmanFord(int start) {

            vector<int>& dist = mMinimumDists;

            fill(dist, INF);
            dist[start] = 0;

            for (int i = 0; i < mNodeNum; ++i) {
                bool update = false;
                for (sptr<vnode> node : mNodes) {
                    for (sptr<vegde> egde : node->getEgde()) {
                        int from = egde->getLeft()->getID();
                        int to = egde->getRight()->getID();
                        if (dist[from] == INF) {
                            continue;
                        }
                        if (dist[node->getID()] + egde->getCost() < dist[to]) {
                            dist[to] = dist[node->getID()] + egde->getCost();
                            update = true;

                            if (i == mNodeNum - 1) {
                                //return false;
                            }
                        }
                    }
                }
                if (!update) {
                    break;
                }
            }
            return true;
        }

        // ダイクストラ法を使ってある頂点から全ての頂点への最短距離を求める
        // 負のコストの辺があると最短距離を計算できない点に注意する
        // O(E*logV)
        void dijkstraSearch(int start) {

            // Minimum distances for each nodes
            vector<int>& dpMinDists = mMinimumDists;
            fill(dpMinDists, INF);

            // Result of the previous visited node
            vector<int>& resultPrev = mPrevNodes;
            fill(resultPrev, -1);

            // Create a priority_queue for search.
            typedef pair<int, pair<int, int>> P; // key: その頂点までの最短距離, value: 頂点の番号, value2: 使ったお金
            priority_queue<P, vector<P>, greater<P>> pq_node;

            // Mark the current node as visited and enqueue it
            pq_node.push(P(0, pair<int, int>(start, 0)));

            dpMinDists[start] = 0;

            while (!pq_node.empty()) {
                P p = pq_node.top();
                pq_node.pop();
                int nowDist = p.first;
                int nowNodeID = p.second.first;
                int nowLeftMoney = p.second.second;

                if (dpMinDists[nowNodeID] < nowDist) {
//                    continue;
                }

                for (sptr<vegde> egde : mNodes[nowNodeID]->getEgde()) {
                    sptr<vnode> nextNode = egde->getRight();
                    int nextNodeID = nextNode->getID();
					int newMoney = nowLeftMoney + egde->getMoney();

					if (newMoney > C) {
						continue;
					}

                    int nextNodeDist = nowDist + egde->getCost();
                    if (nextNodeDist < dpMinDists[nextNodeID]) {
                        dpMinDists[nextNodeID] = nextNodeDist;
                        resultPrev[nextNodeID] = nowNodeID;

                        pq_node.push(P(nextNodeDist, pair<int, int>(nextNodeID, newMoney)));
                    }
                }
            }
        }

        int calcMaxDepth() const {
            pair<int, int> farestNodeData = getFarestNodeID(0);
            pair<int, int> farestNodeData2 = getFarestNodeID(farestNodeData.first);
            return farestNodeData2.second;
        }

        int getNodeNum() const { return mNodeNum; }

        const vector<int>& getMinimumDists() const { return mMinimumDists; }
        const vector<int>& getPrevNodes() const { return mPrevNodes; }
    protected:

        // 引数で受け取ったノードから最も遠いノードのidと距離を返す
        // グラフにループがあると無限ループになるので注意する(つまり木専用)
        pair<int, int> getFarestNodeID(int start) const {
            queue<pair<int, int>> q; // nodeID, このノードまでの距離
            q.push(make_pair(start, 0));
            pair<int, int> finalNodeData;
            vector<bool> opened(mNodeNum);
            fill(opened, false);
            while (!q.empty()) {
                pair<int, int> nodeData = q.front();
                int nodeID = nodeData.first;
                int dist = nodeData.second;
                if (dist > finalNodeData.second) {
                    finalNodeData.second = dist;
                    finalNodeData.first = nodeID;
                }
                q.pop();
                for (sptr<vegde> egde : mNodes[nodeID]->getEgde()) {
                    int id = egde->getRight()->getID();
                    if (opened[id]) {
                        continue;
                    }
                    opened[id] = true;
                    q.push(make_pair(id, dist + egde->getCost()));
                }
            }
            return finalNodeData;
        }

        int mNodeNum;
        bool mUseMaps;
        vector<sptr<vnode>> mNodes;

        vector<int> mMinimumDists;
        vector<int> mPrevNodes;
    };

    // 無向グラフ UnDirected Val Graph.
    class dvgraph : public vgraph {
    public:
        dvgraph(int nodeNum) :
        vgraph(nodeNum) {
        }

        void addEgde(int nodeID1, int nodeID2, int cost, int time) {
            mNodes[nodeID1]->addEgde(make_shared<vegde>(mNodes[nodeID1], mNodes[nodeID2], cost, time));
        }

        void removeEgde(int nodeID1, int nodeID2) {
            mNodes[nodeID1]->removeEgde(nodeID1, nodeID2);
        }
    };

    // 立っているビットの数を返す
    static int bitcount8(unsigned char b8) {
        // 8 bits 限定アルゴリズムを利用している
        //c_assert( 8 == (CHAR_BIT * sizeof( b8 )) );

        b8 = (unsigned char)( ((b8 & 0xAA) >> 1) + (b8 & 0x55) );
        b8 = (unsigned char)( ((b8 & 0xCC) >> 2) + (b8 & 0x33) );
        b8 = (unsigned char)( ((b8 & 0xF0) >> 4) + (b8 & 0x0F) );

        return b8;
    }

    // 立っているビットの数を返す
    static int bitcount16(unsigned short w16) {
        // 16 bits 限定アルゴリズムを利用している
        //c_assert( 16 == (CHAR_BIT * sizeof( w16 )) );

        w16 = (unsigned short)( ((w16 & 0xAAAA) >> 1) + (w16 & 0x5555) );
        w16 = (unsigned short)( ((w16 & 0xCCCC) >> 2) + (w16 & 0x3333) );
        w16 = (unsigned short)( ((w16 & 0xF0F0) >> 4) + (w16 & 0x0F0F) );
        w16 = (unsigned short)( ((w16 & 0xFF00) >> 8) + (w16 & 0x00FF) );

        return w16;
    }

    // 立っているビットの数を返す
    static int bitcount32(unsigned long dw32) {
        // 32 bits 限定アルゴリズムを利用している
        //c_assert( 32 == (CHAR_BIT * sizeof( dw32 )) );

        dw32 = ((dw32 & 0xAAAAAAAA) >>  1) + (dw32 & 0x55555555);
        dw32 = ((dw32 & 0xCCCCCCCC) >>  2) + (dw32 & 0x33333333);
        dw32 = ((dw32 & 0xF0F0F0F0) >>  4) + (dw32 & 0x0F0F0F0F);
        dw32 = ((dw32 & 0xFF00FF00) >>  8) + (dw32 & 0x00FF00FF);
        dw32 = ((dw32 & 0xFFFF0000) >> 16) + (dw32 & 0x0000FFFF);

        return dw32;
    }

}

using namespace ValLib;

int main()
{
	int N, V;
	cin >> N >> C >> V;

	vector<int> S(V);
	vector<int> T(V);
	vector<int> Y(V);
	vector<int> M(V);

	dvgraph graph(N);
	for (int i = 0; i < V; ++i) {
		cin >> S[i];
	}
	for (int i = 0; i < V; ++i) {
		cin >> T[i];
	}
	for (int i = 0; i < V; ++i) {
		cin >> Y[i];
	}
	for (int i = 0; i < V; ++i) {
		cin >> M[i];
	}
	for (int i = 0; i < V; ++i) {
		graph.addEgde(S[i] - 1, T[i] - 1, M[i], Y[i]);
	}

	graph.dijkstraSearch(0);

	int result = graph.getMinimumDists()[N - 1];

	if (result == 1000000) {
		result = -1;
	}

	cout << result << endl;
	
	getchar();
	getchar();
}
yukicoder

結果

テストケース

ソースコード
