soundhound2018_summer_qual D - Saving Snuuk
RPS200000点行きました やったね
解説
こういう問題は、円とスヌークを別々に考えることが大切。
まず、d1[i] = 都市sから都市iまで円を支払って行くときの最小コスト、d2[i] = 都市iから都市tまでスヌークを支払って行くときの最小コストとする。
そして、d1,d2それぞれに対してダイクストラ法をする。
すると、都市sから都市tまで都市iで両替したときの最終的なコスト = 10^15 - (d1[i] + d2[i])が成り立つ。
これが分かれば、あとはセグメント木や累積Maxを使って解ける。
code:hoge.cpp
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000010;
constexpr ll INF= 1000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;
struct edge{
int to;
ll cost;
};
int V; //頂点数
ll d1100010; //都市sから都市iまで円を使って行くときの最小コスト ll d2100010; //都市iから都市tまでスヌークを使って行くときの最小コスト void dijkstra1(int s) {
//greater<P>を指定することでfirstが小さい順に取り出せる
priority_queue<P,vector<P>,greater<P>> que;
fill(d1,d1 + V,INF);
que.push(P(0,s));
while(!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
continue;
}
for(int i = 0;i < G1v.size();i++) { if(d1e.to > d1v + e.cost) { que.push(P(d1e.to,e.to)); }
}
}
}
void dijkstra2(int s) {
//greater<P>を指定することでfirstが小さい順に取り出せる
priority_queue<P,vector<P>,greater<P>> que;
fill(d2,d2 + V,INF);
que.push(P(0,s));
while(!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
continue;
}
for(int i = 0;i < G2v.size();i++) { if(d2e.to > d2v + e.cost) { que.push(P(d2e.to,e.to)); }
}
}
}
//抽象化セグ木。基本的には普通のセグ木でいいが、乗せるものがintじゃない（例えば1次方程式とか）に使える
template <class T>
class SegTree {
int n; // 葉の数
vector<T> data; // データを格納するvector
T def; // 初期値かつ単位元
function<T(T, T)> operation; // 区間クエリで使う処理
function<T(T, T)> update; // 点更新で使う処理
// 区間[a,b)の総和。ノードk=[l,r)に着目している。
T _query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return def; // 交差しない
if (a <= l && r <= b)
return datak; // a,l,r,bの順で完全に含まれる else {
T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
return operation(c1, c2);
}
}
public:
// _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
// _update:更新関数
SegTree(size_t _n, T _def, function<T(T, T)> _operation,
function<T(T, T)> _update)
: def(_def), operation(_operation), update(_update) {
n = 1;
while (n < _n) {
n *= 2;
}
data = vector<T>(2 * n - 1, def);
}
// 場所i(0-indexed)の値をxで更新
void change(int i, T x) {
i += n - 1;
datai = update(datai, x); while (i > 0) {
i = (i - 1) / 2;
}
}
// [a, b)の区間クエリを実行
T query(int a, int b) {
return _query(a, b, 0, 0, n);
}
// 添字でアクセス
T operator[](int i) {
}
};
int main() {
cin >> V;
int M;
cin >> M;
int s,t;
cin >> s >> t;
s--;
t--;
for(int i = 0;i < M;i++) {
int u,v;
ll a,b;
cin >> u >> v >> a >> b;
u--;
v--;
G1u.push_back(edge{v,a}); G1v.push_back(edge{u,a}); G2u.push_back(edge{v,b}); G2v.push_back(edge{u,b}); }
dijkstra1(s);
dijkstra2(t);
SegTree<ll> seg(V,INF,
[](ll a,ll b){return max(a,b);},
[](ll a,ll b){return b;});
for(int i = 0;i < V;i++) {
seg.change(i,1000000000000000 - (d1i + d2i)); }
for(int i = 0;i < V;i++) {
cout << seg.query(i,V) << endl;
}
}