提出 #23252700

---

ソースコード 拡げる

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Edge {
    int to;
    long long C, D;
};
typedef vector<vector<Edge>> Graph;

void solve(long long N, long long M, std::vector<long long> A,
           std::vector<long long> B, std::vector<long long> C,
           std::vector<long long> D) {
    Graph G(N);
    for (int i = 0; i < M; i++) {
        G[A[i] - 1].emplace_back(Edge{B[i] - 1, C[i], D[i]});
    }

    std::vector<long long> dist(N, numeric_limits<long long>::max());
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        queue;
    queue.push({0, 0});
    while (!queue.empty()) {
        auto p = queue.top();
        queue.pop();
        if (dist[p.second] <= p.first) continue;
        dist[p.second] = p.first;

        for (const auto e : G[p.second]) {
            double low = p.first;
            double high = numeric_limits<long long>::max() / 100;
            for (int i = 0; i < 500; i++) {
                double c1 = (low * 2 + high) / 3;
                double c2 = (low + high * 2) / 3;

                double y1 = c1 + e.C + (long long)(e.D / (c1 + 1));
                double y2 = c2 + e.C + (long long)(e.D / (c2 + 1));
                if (y1 > y2)
                    low = c1;
                else
                    high = c2;
            }
            // printf("low = %lf d = %lf high = %lf d = %lf\n", low,
            //        low + e.C + e.D / (low + 1), high,
            //        high + e.C + e.D / (high + 1));
            long long t = std::max(p.first, (long long)low);
            long long d = t + e.C + e.D / (t + 1);
            t++;
            d = min(d, t + e.C + e.D / (t + 1));
            queue.push({d, e.to});
        }
    }
    if (dist[N - 1] != numeric_limits<long long>::max()) {
        printf("%lld\n", dist[N - 1]);
    } else {
        printf("-1\n");
    }
}

// Generated by 2.3.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
    long long N;
    std::scanf("%lld", &N);
    long long M;
    std::scanf("%lld", &M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    std::vector<long long> C(M);
    std::vector<long long> D(M);
    for (int i = 0; i < M; i++) {
        std::scanf("%lld", &A[i]);
        std::scanf("%lld", &B[i]);
        std::scanf("%lld", &C[i]);
        std::scanf("%lld", &D[i]);
    }
    solve(N, M, std::move(A), std::move(B), std::move(C), std::move(D));
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘void solve(long long int, long long int, std::vector<long long int>, std::vector<long long int>, std::vector<long long int>, std::vector<long long int>)’:
./Main.cpp:33:44: warning: narrowing conversion of ‘(B.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)’ from ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
   33 |         G[A[i] - 1].emplace_back(Edge{B[i] - 1, C[i], D[i]});
./Main.cpp: In function ‘int main()’:
./Main.cpp:83:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   83 |     std::scanf("%lld", &N);
      |     ~~~~~~~~~~^~~~~~~~~~~~
./Main.cpp:85:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   85 |     std::scanf("%lld", &M);
      |     ~~~~~~~~~~^~~~~~~~~~~~
./Main.cpp:91:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   91 |         std::scanf("%lld", &A[i]);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:92:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   92 |         std::scanf("%lld", &B[i]);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:93:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   93 |         std::scanf("%lld", &C[i]);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:94:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   94 |         std::scanf("%lld", &D[i]);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~

ジャッジ結果