[SoundHound 2018 Qual D] Saving Snuuk 题解

· · 题解

注意到我们可以枚举 Kenkoooo 兑换钱币的那个中转点。

记 x_i 为从起点 s 到中转站 i 使用日元的最少总花费，y_i 为从中转站 i 到终点 t 使用 snuuk 的最少总花费。因为边是双向的，所以从 s 和 t 为源点分别跑最短路（推荐使用 Dijkstra 算法）可以便捷地求出所有的 x_i 和 y_i。

然后枚举那个中转点，记第 i 次旅行（即在 i-1 年后的那次旅行）的最小花费为 f_i，根据兑换局的关闭时间，有 f_i=\min\{f_{i+1},x_i+y_i\}，答案即为 10^{15}-f_i。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
vector<vector<tpi> > g;
void f(int s,bool o,vector<int> &d){
  vector<bool> b(d.size());
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.emplace(d[s]=0,s);
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(b[u])continue; b[u]=true;
    for(auto [i,a,b]:g[u])
      if(d[i]>d[u]+(o?a:b))
        q.emplace(d[i]=d[u]+(o?a:b),i);
  }
} // 跑最短路
main(){
  ios::sync_with_stdio(false);
  int n,m,s,t; cin>>n>>m>>s>>t; g.resize(n);
  for(int i=1;i<=m;i++){
    int a,b,c,d; cin>>a>>b>>c>>d;
    g[--a].emplace_back(--b,c,d);
    g[b].emplace_back(a,c,d);
  } // 建图
  vector<int> d1(n,1e15),d2(n,1e15),c(n+1);
  f(s-1,1,d1),f(t-1,0,d2),c[n]=1e15;
  for(int i=n-1;~i;i--)
    c[i]=min(c[i+1],d1[i]+d2[i]); // 枚举
  for(int i=0;i<n;i++)
    cout<<(int)1e15-c[i]<<endl;
  return 0;
}