Submission #57343801

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int,int> Pair;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD =  998244353; // 1000000007;

template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}

template <class T = int>
struct Graph {
    struct Edge {
        int from, to, id = -1;
        T cost = 1;

        Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {}
    };

    Graph(int N) : N(N) {
        edges.resize(N);
    }

    void add_directed_edge(int from, int to, T cost = 1, int id = -1) {
        Edge e(from, to, cost, id);
        edges[from].push_back(e);
    }

    void add_edge(int u, int v, T cost = 1, int id = -1) {
        add_directed_edge(u, v, cost, id);
        add_directed_edge(v, u, cost, id);
    }

    std::vector<T> dijkstra(int s = 0) {
        std::vector<T> dist(N, -1);
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> q;

        auto push = [&](int v, T cost) {
            if (dist[v] < 0 or cost < dist[v]) {
                dist[v] = cost;
                q.emplace(cost, v);
            }
        };

        push(s, 0);
        while (!q.empty()) {
            auto [cost, v] = q.top();
            q.pop();

            if (dist[v] < cost)
                continue;

            for (Edge &e : edges[v]) {
                push(e.to, cost + e.cost);
            }
        }

        return dist;
    }

  private:
    int N;
    std::vector<std::vector<Edge>> edges;
};

void Main(){
    int N,M,S; cin >> N >> M >> S;
    int K = 2500;
    chmin(S, K-1);
    Graph<ll> g(N * K);
    REP(_,M) {
        int u,v,a,b; cin >> u >> v >> a >> b;
        u--; v--;
        REP(i,K) {
            if(i - a >= 0) {
                g.add_directed_edge(i * N + u, (i-a) * N + v, b);
                g.add_directed_edge(i * N + v, (i-a) * N + u, b);
            }
        }
    }
    REP(i,N) {
        int c,d; cin >> c >> d;
        REP(j,K-1) {
            g.add_directed_edge(j * N + i, min(K-1, j+c) * N + i, d);
        }
    }
    VL dist = g.dijkstra(S * N);
    FOR(i,1,N) {
        ll ans = LINF;
        REP(j,K) chmin(ans, dist[j * N + i]);
        cout << ans << en;
    }
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    while(t--) Main();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In instantiation of ‘Graph<T>::Edge::Edge(int, int, T, int) [with T = long long int]’:
Main.cpp:48:14:   required from ‘void Graph<T>::add_directed_edge(int, int, T, int) [with T = long long int]’
Main.cpp:99:36:   required from here
Main.cpp:38:11: warning: ‘Graph<long long int>::Edge::cost’ will be initialized after [-Wreorder]
   38 |         T cost = 1;
      |           ^~~~
Main.cpp:37:23: warning:   ‘int Graph<long long int>::Edge::id’ [-Wreorder]
   37 |         int from, to, id = -1;
      |                       ^~
Main.cpp:40:9: warning:   when initialized here [-Wreorder]
   40 |         Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {}
      |         ^~~~

Judge Result