Codeforce 144 D. Missile Silos 解析(思維、最短路)

今天我們來看看CF144D
題目連結

題目
略，請直接看原題。

前言

a?

想法

首先由於邊權是非負的，所以我們用$Dijkstra$先把最短路徑樹生出來(順便紀錄每個點在這棵樹上的父節點)，接著只要從$s$開始的最短路長度恰好是$l$的點都可以使答案加一。
最後遍歷所有邊，並仔細判斷這個邊上可能有幾個點(例如要記得判斷我們走的路不是往最短路徑樹的樹根上走)，詳細可以直接看程式碼。

程式碼:

const int _n=1e5+10;  
int t,n,m,s,l,u,v,w,dis[_n],fa[_n];  
vector<PII> G[_n];  
bool vis[_n];  
struct WE{  
  int f,t,d;  
  bool operator<(const WE& rhs)const{return d>rhs.d;}  
} e[_n];  
priority_queue<WE> pq;  
ll ans;  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n>>m>>s;rep(i,0,m){cin>>u>>v>>w;G[u].pb({v,w}),G[v].pb({u,w});e[i]={u,v,w};}  
  cin>>l;rep(i,1,n+1)dis[i]=1e9;  
  dis[s]=0;for(PII uu:G[s])pq.push({s,uu.fi,uu.se});vis[s]=1;  
  rep(_,0,n-1){  
    WE now=pq.top();pq.pop();  
    if(vis[now.t]){_--;continue;}  
    dis[now.t]=now.d;vis[now.t]=1;fa[now.t]=now.f;  
    for(PII uu:G[now.t])if(!vis[uu.fi])pq.push({now.t,uu.fi,now.d+uu.se});  
  }rep(i,1,n+1)if(dis[i]==l)ans++;  
  rep(i,0,m){  
    int a=l-dis[e[i].f],b=l-dis[e[i].t];  
    if(fa[e[i].f]!=e[i].t and dis[e[i].f]<l and dis[e[i].f]+e[i].d>l and dis[e[i].f]+a<=dis[e[i].t]+e[i].d-a)ans++;  
    if(fa[e[i].t]!=e[i].f and dis[e[i].t]<l and dis[e[i].t]+e[i].d>l and dis[e[i].t]+b<=dis[e[i].f]+e[i].d-b)ans++;  
    if(fa[e[i].f]!=e[i].t and dis[e[i].f]<l and dis[e[i].f]+e[i].d>l and  
      dis[e[i].t]+b<=dis[e[i].f]+e[i].d-b and dis[e[i].f]+a<=dis[e[i].t]+e[i].d-a   
      and fa[e[i].t]!=e[i].f and dis[e[i].t]<l and dis[e[i].t]+e[i].d>l   
      and l-dis[e[i].f]==e[i].d-l+dis[e[i].t])ans--;  
  }cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission