Try   HackMD

【CSES】1202. Investigation

題目連結

時間複雜度

  • O(ElogV)

解題想法

這題我第一次看起來覺得很複雜,但是仔細想一下之後就會發現其實沒有很難解,只是將 Dijkstra 搭配上 DP 就可以處理掉了

然後在進行 Dijkstra 的時候要同時追蹤下面四個東西

  1. 最短距離:dis[]
  2. 最短距離的解數量: routes[]
  3. 最短距離且最少的班機數: minf[]
  4. 最短距離且最少的班機數: maxf[]

對於每個節點

v,我們都會考慮他的所有權重為
w
的鄰居
u
,當我們可以鬆弛邊
vu
(dis[v] > dis[u] + w)時,就將變數的值更改成下面這樣

  1. 最短距離:dis[v] = dis[u] + w
  2. 最短距離的解數量: routes[v] = routes[u]
  3. 最短距離且最少的班機數: minf[v] = minf[u] + 1
  4. 最短距離且最少的班機數: maxf[v] = maxf[v] + 1

但跟平常的 Dijkstra 不一樣的是我們還必須考慮到 dis[v] = dis[u] + w 的情況(因為你不會知道當前是不是最段距離),所以當 dis[v] = dis[u] + w 成立時,我們將值更新成下變這樣

  1. 最短距離:dis[v] 不更新
  2. 最短距離的解數量: routes[v] = ( routes[v] + routes[u] ) % Mod ➨ 這邊記得取模
  3. 最短距離且最少的班機數: minf[v] = min( minf[v], minf[u] + 1 )
  4. 最短距離且最少的班機數: maxf[v] = max( maxf[v], maxf[u] + 1 )

完整程式

/* Question : CSES 1202. Investigation */ #include<bits/stdc++.h> using namespace std; #define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pirq(type) priority_queue<type, vector<type>, greater<type>> #define mem(x, value) memset(x, value, sizeof(x)); #define pii pair<int, int> #define pll pair<long long, long long> #define pdd pair<double, double> #define pb push_back #define f first #define s second #define int long long const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; const int MAXN = 1e5 + 50; const int Mod = 1e9 + 7; int n, m, u, v, w, dis[MAXN]; vector<vector<pii>> graph; struct Node{ int maxf = 0, minf = 0, routes = 0; } dp[MAXN]; void dij( int root ){ pirq(pii) pq; pq.push({0, root}); dis[root] = 0; dp[root].routes = 1; while( !pq.empty() ){ int d = pq.top().f; int node = pq.top().s; pq.pop(); if( d > dis[node] ) continue; for( auto i : graph[node] ){ int v = i.f; int w = i.s; // Weight if( d + w == dis[v] ){ dp[v].routes = ( dp[v].routes + dp[node].routes ) % Mod; dp[v].maxf = max( dp[v].maxf, dp[node].maxf + 1); dp[v].minf = min( dp[v].minf, dp[node].minf + 1); }else if( d + w < dis[v] ){ dis[v] = d + w; dp[v].routes = dp[node].routes; dp[v].maxf = dp[node].maxf + 1; dp[v].minf = dp[node].minf + 1; pq.push({dis[v], v}); } } } } signed main(){ opt; cin >> n >> m; graph.resize(n+5); for( int i = 0 ; i < m ; i++ ){ cin >> u >> v >> w; graph[u].pb({v, w}); } mem(dis, 0x3F); dij(1); cout << dis[n] << " " << dp[n].routes << " " << dp[n].minf << " " << dp[n].maxf << "\n"; }