Try   HackMD

【CSES】1195. Flight Discount

題目連結

時間複雜度

  • O(|E|log|E|)

解題想法

這題的話其實有 DP 跟雙圖兩種解法,這題我用的是雙圖的解法,下面我會簡單敘述一下何謂雙圖解法還有雙圖的可能性解釋

甚麼是雙圖解法

雙圖解法顧名思義就是用兩張相同的圖下去實作,透過連接兩張圖來進行實作,製作出現下面這張圖

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

透過複製題目給的圖之後,將圖一中的所有邊複製一條牽到圖二,並將邊權設為原本邊權的一半(題目要求)就可以了

雙圖為甚麼可以解決這題

  1. 保證走到終點只會經過一次折半邊
  2. 保證一次 Dijkstra 之內可以找到解

完整程式

/* Question : CSES 1195. Flight Discount */ #include<bits/stdc++.h> using namespace std; #define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define mem(x, value) memset(x, value, sizeof(x)); #define pii pair<int, int> #define pdd pair<double, double> #define f first #define s second #define pb push_back #define pirq(type) priority_queue<type, vector<type>, greater<type>> #define int long long const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; const int MAXN = 2e5 + 50; const int Mod = 1e9 + 7; int n, m, a, b, w, dis[MAXN]; vector<vector<pii>> graph; void dij( int root ){ pirq(pii) pq; pq.push({0, root}); dis[root] = 0; 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; if( d + w < dis[v] ){ dis[v] = d + w; pq.push({dis[v], v}); } } } } signed main(){ opt; cin >> n >> m; graph.resize(n+n+5); for( int i = 0 ; i < m ; i++ ){ cin >> a >> b >> w; graph[a].pb({b, w}); graph[a].pb({b+n, w/2}); graph[a+n].pb({b+n, w}); } mem(dis, 0x3F); dij(1); cout << dis[n+n] << "\n"; }