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

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

題目
略，請直接看原題。

前言

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

想法

觀察到，如果想要整個最短路徑樹不變，就代表說，對於$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