Codeforce 449 B. Jzzhu and Cities 解析(思維、最短路)

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

題目
略，請直接看原題。

前言

這題讓我對Dijkstra的運作有更深一步的了解。

@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog

想法

觀察到，如果想要整個最短路徑樹不變，就代表說，對於\(1\rightarrow i\)的火車路線，長度\(y\)，如果到\(i\)的最短路徑小於\(y\)，這個火車路徑就可以拿掉。如果最短路徑剛好等於\(y\)，就要看看，是不是有不是這條火車路徑的另一條路徑可以以最短路徑到達\(i\)，如果有的話就可以捨去這條火車路徑。
由於這題的\(n\le1e5\)，基本上我們能想到的，複雜度夠低的最短路徑算法只有Dijkstra可以勝任了。因此以下我們來詳細敘述在這題該如何使用Dijkstra。
主要比較會讓人不知道該如何下手的，應該是如何判斷有沒有多於一條的最短路徑。Dijkstra的作法是，每次找出和最短路徑樹相鄰的，距離點\(1\)最近的點(用priority_queue)，並且連上去。也就是說，在把一個點push進priority_queue之前，我們會先看看這個點是否已經在樹上了。
並且注意到，我們對於圖上的每一條邊都會考慮到，並且考慮一條邊(\(u\rightarrow v\))時，我們必定已經知道點\(1\)到點\(u\)的最短路徑了。也就是說，如果\(1\rightarrow v\)的最短路有兩條，那麼我們只要在檢查每條邊要不要放進priority_queue之時，再檢查一下是否目前到\(v\)的最短路徑是火車路線，並且另一條路徑長度(小於)等於火車鐵軌長度，如果是的話即可拋棄掉這條火車鐵軌。

程式碼:

const int _n=1e5+10;
const ll inf=1e18;
int t,n,m,k,u,v,x,s,y,ans,train[_n];
ll dis[_n];
struct WE{int to,w;};
struct W{ll f,t,w;
bool operator<(const W& rhs)const{return w>rhs.w;}};
vector<WE> G[_n];
priority_queue<W> pq;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m>>k;rep(i,0,m){cin>>u>>v>>x;G[u].pb({v,x}),G[v].pb({u,x});}
  rep(i,0,k){
    cin>>s>>y;
    if(!train[s])train[s]=y;
    else if(train[s])ans++,train[s]=min(train[s],y);
  }rep(i,1,n+1)dis[i]=inf;
  rep(i,2,n+1)if(train[i])pq.push({0,i,train[i]});
  pq.push({0,1,0});while(!pq.empty()){
    W now=pq.top();pq.pop();if(dis[now.t]!=inf)continue;
    dis[now.t]=now.w;
    for(WE& u:G[now.t]){
      if(dis[u.to]==inf)pq.push({now.t,u.to,dis[now.t]+u.w});
      if(train[u.to] and dis[now.t]+u.w<=train[u.to])ans++,train[u.to]=0;
    }
  }cout<<ans<<'\n';
  return 0;
}

標頭、模板請點Submission看(事實上priority_queue用WE這個struct就夠了，不用多存一個f)
Submission