結果

問題 No.2739 Time is money
ユーザー ilovenaomiilovenaomi
提出日時 2024-04-21 06:51:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,310 bytes
コンパイル時間 2,657 ms
コンパイル使用メモリ 216,516 KB
実行使用メモリ 92,348 KB
最終ジャッジ日時 2024-10-13 05:35:38
合計ジャッジ時間 22,885 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 580 ms
38,528 KB
testcase_03 WA -
testcase_04 AC 555 ms
37,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 1,114 ms
63,928 KB
testcase_11 WA -
testcase_12 AC 1,153 ms
92,248 KB
testcase_13 AC 1,128 ms
92,312 KB
testcase_14 AC 1,108 ms
92,348 KB
testcase_15 WA -
testcase_16 AC 530 ms
69,696 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 1,123 ms
59,452 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <=(int)(n); i++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
using namespace std;

map<pair<int,int>, ll> mpc,mpt;
ll ans = -1;
ll x;
void dfs(int goal,vector<vector<int>>& graph,vector<bool>&passed, 
            int start, ll cost, ll time){
    if( start == goal){
        ll atime = cost / x;
        if( cost % x != 0) atime++;

        if( ans == -1){
            ans = atime+time;
        }else{
            ans = min(ans,atime+time);
        }


        return ;
    }
    passed[start] = true;
    for( auto nx: graph[start]){
        if( passed[nx] == false){
            dfs(goal,graph,passed,nx, 
                cost+mpc[{start,nx}],
                time+mpt[{start,nx}]);
        }  
    }
}

int main() {
    int n,m;
    cin >> n >> m >> x;
    vector<vector<int>> graph(n);
    rep(i,m){
        int u,v;
        ll c,t;
        cin >> u >> v >> c >> t;
        v--;
        u--;
        mpt[{u,v}] = t;
        mpc[{u,v}] = c;
        mpt[{v,u}] = t;
        mpc[{v,u}] = c;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<bool> passed(n,false);
    ans = -1;
    dfs(n-1,graph,passed,0,0,0);

    cout << ans << endl;
}
0