Language: C++


#include "bits/stdc++.h"
using namespace std;
#define int long long

#define FOR(i, a, b) for(int i=a;i<b;i++)
#define rep(i, b) FOR(i,0,b)
#define INF LLONG_MAX
#define all(a) (a).begin,(a).end()

int N,M,S,T;

struct Edge{
    int to,cost;
    Edge(int to,int cost):to(to),cost(cost){}
};
struct idxcost{
    int idx,cost;
    idxcost(int idx,int cost):idx(idx),cost(cost){}

    bool operator < (const idxcost& s)const{
        return (cost < s.cost);
    }
};
vector<Edge> G_en[112345];
vector<Edge> G_snu[112345];
int d[112345];
int d_snu[112345];
int ans[112345];
int pans[112345];

void dijkstra_en(int s){
    //rep(i,112345)d[i]=0;
    priority_queue<idxcost,vector<idxcost>,greater<idxcost>> pq;
    fill(d,d+112345,INF);
    d[s]=0;
    pq.push(idxcost(s,0));
    while(!pq.empty()){
        idxcost p = pq.top();pq.pop();
        int v=p.idx;
        if(d[v]<p.cost)continue;

        for(int i=0;i<G_en[v].size();i++){
            Edge e=G_en[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                pq.push(idxcost(e.to,d[e.to]));
            }
        }
    }
}

void dijkstra_snu(int s){

    priority_queue<idxcost,vector<idxcost>,greater<idxcost>> pq;
    fill(d_snu,d_snu+112345,INF);
    d_snu[s]=0;
    pq.push(idxcost(s,0));
    while(!pq.empty()){
        idxcost p = pq.top();pq.pop();
        int v=p.idx;
        if(d_snu[v]<p.cost)continue;

        for(int i=0;i<G_snu[v].size();i++){
            Edge e=G_snu[v][i];
            if(d_snu[e.to]>d_snu[v]+e.cost){
                d_snu[e.to]=d_snu[v]+e.cost;
                pq.push(idxcost(e.to,d_snu[e.to]));
            }
        }
    }

}

signed main(){

    cin>>N>>M>>S>>T;
    S--;T--;

    rep(i,M){
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        //0-indexedに
        u--;v--;
        G_en[u].push_back(Edge(v,a));
        G_en[v].push_back(Edge(u,a));
        G_snu[u].push_back(Edge(v,b));
        G_snu[v].push_back(Edge(u,b));

    }
    dijkstra_en(S);
    dijkstra_snu(T);

    
    rep(i,N){
        //両替する場所をiとした時のs->i + j->t

        int en_dis=d[i];
        int snu_dis=d_snu[i];

        ans[i]=en_dis+snu_dis;

    }


    int tans=1000000000000000;
    pans[N]=tans;
    for(int i=N-1;i>=0;i--){
        pans[i]=min(pans[i+1],ans[i]);
    }

    rep(i,N){
        //i番目からの都市が使える
        cout<<1000000000000000-pans[i]<<endl;

    }



}

Compiler output:
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_function.h: In instantiation of 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = idxcost]':
/usr/include/c++/14/bits/predefined_ops.h:196:23:   required from 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<idxcost*, std::vector<idxcost> >; _Value = idxcost; _Compare = std::greater<idxcost>]'
  196 |         { return bool(_M_comp(*__it, __val)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<idxcost*, vector<idxcost> >; _Distance = long int; _Tp = idxcost; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<idxcost> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:216:23:   required from 'void std::push_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<idxcost*, vector<idxcost> >; _Compare = greater<idxcost>]'
  216 |       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  217 |                        _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:747:16:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(value_type&&) [with _Tp = idxcost; _Sequence = std::vector<idxcost>; _Compare = std::greater<idxcost>; value_type = idxcost]'
  747 |         std::push_heap(c.begin(), c.end(), comp);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:37:12:   required from here
   37 |     pq.push(idxcost(s,0));
      |     ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:395:20: error: no match for 'operator>' (operand types are 'const idxcost' and 'const idxcost')
  395 |       { return __x > __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1058:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1058 |     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1058:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:395:20: note:   'const idxcost' is not derived from 'const std::pair<_T1, _T2>'
  395 |       { return __x > __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:462:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  462 |     operator>(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:462:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:395:20: note:   'const idxcost' is not derived from 'const std::reverse_iterator<_Iterator>'
  395 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:507:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  507 |     operator>(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:507:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:395:20: note:   'const idxcost' is not derived from 'const std::reverse_iterator<_Iterator>'
  395 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1714:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1714 |     operator>(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1714:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:395:20: note:   'const idxcost' is not derived from 'const std::move_iterator<_IteratorL>'
  395 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1774:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1774 |     operator>(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1774:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:395:20: note:   'const idxcost' is not derived from 'const std::move_iterator<_IteratorL>'
  395 |       { return __x > __y; }
      |                ~~~~^~~~~