图论|通信线路「分层图最短路」||「二分答案 + 巧妙的建图跑最短路」最短路|分层图最短路|算法

通信线路题目描述：

n个点，m条双向边，求1到n的路程中价格第k+1大的边的权值最小是多少，如果路径数量小于k+1，则输出0

思路1:分层图最短路

【图论|通信线路「分层图最短路」||「二分答案 + 巧妙的建图跑最短路」】求第k+1大的边，则可以转换成让k条边的权值是0，再求权值最大值的最小值，考虑分层图最短路，同一层内普通建图，但是层与层之间对应的点建权值为0的边，此外还需要给n * i到n * (i + 1) 之间建权值为0的边，来解决路径数量不足k+1的情况，然后跑最短路，输出dis[n * (k + 1)]的值即可

#include using namespace std; #define endl '\n' #define inf 0x3f3f3f3f #define mod 1000000007 #define m_p(a,b) make_pair(a, b) #define mem(a,b) memset((a),(b),sizeof(a)) #define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)typedef long long ll; typedef pair pii; #define MAX 2000000 + 50 int n, m, k; int tot; int head[MAX]; struct ran{ int to, nex, val; }tr[MAX]; inline void add(int u, int v, int c){ tr[++tot].to = v; tr[tot].val = c; tr[tot].nex = head[u]; head[u] = tot; }int dis[MAX]; bool vis[MAX]; void dijkstra(int s, int t){ priority_queue, greater>q; mem(dis, inf); q.push(m_p(0, s)); dis[s] = 0; while (!q.empty()) { auto [d, u] = q.top(); q.pop(); if(vis[u])continue; vis[u] = 1; for(int i = head[u]; i; i = tr[i].nex){ int v = tr[i].to; if(dis[v] > max(tr[i].val, dis[u])){ dis[v] = max(tr[i].val, dis[u]); q.push(m_p(dis[v], v)); } } } if(dis[t] == inf)cout << -1 << endl; else cout << dis[t] << endl; }void work(){ cin >> n >> m >> k; for(int i = 1, a, b, c; i <= m; ++i){ cin >> a >> b >> c; add(a, b, c); add(b, a, c); for(int j = 1; j <= k; ++j){ add(a + (j - 1) * n, b + j * n, 0); add(b + (j - 1) * n, a + j * n, 0); add(a + j * n, b + j * n, c); add(b + j * n, a + j * n, c); } } for(int i = 1; i <= k; ++i)add(i * n, (i + 1) * n, 0); dijkstra(1, n * k + n); }int main(){ io; work(); return 0; }

思路2:二分答案 + 最短路

二分权值p，巧妙的建图：权值大于p的边的权值为1，权值小于等于p的权值为0，这样跑最短路得到的就是最少需要几条大于p的边，拿它和k进行比较来作为二分的check函数，非常妙

#include using namespace std; #define endl '\n' #define inf 0x3f3f3f3f #define mod 1000000007 #define m_p(a,b) make_pair(a, b) #define mem(a,b) memset((a),(b),sizeof(a)) #define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)typedef long long ll; typedef pair pii; #define MAX 300000 + 50 int n, m, k; int a, b, c; int tot; int head[MAX]; struct ran{ int to, nex, val; }tr[MAX]; inline void add(int u, int v, int c){ tr[++tot].to = v; tr[tot].val = c; tr[tot].nex = head[u]; head[u] = tot; }bool vis[1005]; int dis[1005]; int dijkstra(int s, int mid){ priority_queue, greater >q; mem(dis, inf); mem(vis, 0); q.push(m_p(0, s)); dis[s] = 0; while (!q.empty()) { auto [d, u] = q.top(); q.pop(); if(vis[u])continue; vis[u] = 1; for(int i = head[u]; i; i = tr[i].nex){ int v = tr[i].to; int p = 0; if(tr[i].val > mid)p = 1; if(dis[v] > dis[u] + p){ dis[v] = dis[u] + p; q.push(m_p(dis[v], v)); } } } return dis[n]; }bool judge(int mid){ if(dijkstra(1, mid) <= k)return true; return false; }void work(){ cin >> n >> m >> k; for(int i = 1; i <= m; ++i){ cin >> a >> b >> c; add(a, b, c); add(b, a, c); }int l = 0, r = 1000001; while (l <= r) { int mid = (l + r) / 2; if(judge(mid))r = mid - 1; else l = mid + 1; } if(dis[n] == inf)cout << -1 << endl; else cout << l << endl; }int main(){ io; work(); return 0; }