SoundHound Inc. Programming Contest 2018 -Masters Tournament- D - Saving Snuuk (copy)
2020/2/4
ポイント
どこで両替するかを全探索したくなる
円とスヌークで別々に重み付き無向グラフを作り、ダイクストラすることを考える
どこかで両替した後はスヌークのグラフをたどっていくことになるので、後半はスヌークで考えたい
sからダイクストラすればどこに何円でいけるかがわかる
i -> tとt ->iは同じなので、tからダイクストラすることを考えれば良い(ここ天才)
s - > (どこか) - > tという移動をイメージする
だんだんと候補が減っていくわけで、N-1年後には最後のところで両替するしか方法がない
一年前のN-2年後には二つの候補があるわけなので、前年とのmaxを取れば良い
このように、時間を前にたどって行った時にだんだんと候補が減っていく場合は、逆に考えることで候補が増えていく方向に考えていくと計算が楽になる
解説記事
code:c++
using namespace std;
#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(a) (a).begin(),(a).end() typedef long long ll;
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; }
const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);
const int dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; /*------------------------------------/
for library*/
template<class T> class Dijkstra {
public:
int N;
T inf;
vector<T> cost;
vector<vector<pair<T, int>>> edge;
Dijkstra(const int N, T inf) : N(N), inf(inf),cost(N), edge(N) {
}
void make_edge(int from, int to, T w) {
edgefrom.push_back({ w,to }); }
void solve(int start) {
for(int i = 0; i < N; ++i) costi = inf; priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
pq.push({ 0,start });
while (!pq.empty()) {
T v = pq.top().first;
int from = pq.top().second;
pq.pop();
for (auto u : edgefrom) { T w = v + u.first;
int to = u.second;
pq.push({ w,to });
}
}
}
return;
}
};
/*
使い方
1. まずインスタンス生成
重みの型、頂点の数、距離の無限大のINFLL
Dijkstra<ll> d(N, INFLL);
2. 辺を貼る
iからjに重みwの辺を貼る場合
d.make_edge(i,j,w);
3. 頂点sから解く
d.solve(s);
4. sからgの距離
GigaCode2019 E - 車の乗り継ぎ
*/
/*------------------------------------*/
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
ll N,M,s,t;
cin>>N>>M>>s>>t;
Dijkstra<ll> d1(N, INFLL);
Dijkstra<ll> d2(N, INFLL);
s--;t--;
rep(i,M){
ll u,v,a,b;
cin>>u>>v>>a>>b;
u--;v--;
d1.make_edge(u,v,a);
d1.make_edge(v,u,a);
d2.make_edge(u,v,b);
d2.make_edge(v,u,b);
}
d1.solve(s);
d2.solve(t);
ll money = 1e15;
ll maxx = 0;
vector<ll> ans(N);
for(int i = N-1; i >= 0; i--){
ll cost = d1.costi + d2.costi; ll tmp = money - cost;
chmax(maxx, tmp);
}
rep(i,N){
}
}