域名证书查询网站,厦门网站建设工程,网站建设内容模板下载,上海商场网站开发一、题目大意
我们有n个点#xff0c;p条边#xff0c;最小化从1到n之间的路径的第k1大的数#xff08;当路径不超过k时就是0#xff09;
二、解题思路
我们首先用dijkstra过一遍#xff0c;判断从1能不能到n#xff0c;不能直接输出-1结束。
1能到达n的话#xff0…一、题目大意
我们有n个点p条边最小化从1到n之间的路径的第k1大的数当路径不超过k时就是0
二、解题思路
我们首先用dijkstra过一遍判断从1能不能到n不能直接输出-1结束。
1能到达n的话就对二分第k1大的边进行二分left选-1right选最大的边的长度1这里我left一开始选取的时最小边-1后来发现当k比较大时结果可能是0
二分的依据如下
设二分的值为mid
记录从1到n的路径中必走的大于mid的值的数量
如果超过了k那么放大mid
如果小于等于k那么缩小mid同时记录这样不断循环直到找到一个临界值limit
当midlimit时大于mid的边小于等于k个
当midlimit-1时大于mid的边超过k个
那么limit一定就是第k1大的边输出最后一个大于mid的边数小于等于k的mid即可
三、代码
#include iostream
#include algorithm
#include queue
#include vector
using namespace std;
typedef pairint, int P;
vectorP edges[1007];
bool used[1007];
int n, p, k, d[1007], inf 0x3f3f3f3f, maxt 0;
void input()
{int from, to, cost;scanf(%d%d%d, n, p, k);for (int i 0; i p; i){scanf(%d%d%d, from, to, cost);edges[from - 1].push_back(P(cost, to - 1));edges[to - 1].push_back(P(cost, from - 1));maxt max(cost, maxt);}
}
bool judgeByDijkstra(int mid)
{for (int i 0; i n; i){d[i] inf;used[i] false;}d[0] 0;priority_queueP, vectorP, greaterP que;que.push(P(d[0], 0));while (!que.empty()){P current que.top();que.pop();if (used[current.second] || current.first d[current.second]){continue;}used[current.second] true;for (int i 0; i edges[current.second].size(); i){P toEdge edges[current.second][i];int relativeEdge toEdge.first mid ? 1 : 0;if (d[current.second] relativeEdge d[toEdge.second]){d[toEdge.second] d[current.second] relativeEdge;que.push(P(d[toEdge.second], toEdge.second));}}}return d[n - 1] k;
}
void binarySearch()
{int left -1, right maxt 1;while (left 1 right){int mid (left right) / 2;if (judgeByDijkstra(mid)){right mid;}else{left mid;}}printf(%d\n, right);
}
bool judgeIfCanGet()
{for (int i 0; i n; i){d[i] inf;used[i] false;}d[0] 0;priority_queueP, vectorP, greaterP que;que.push(P(d[0], 0));while (!que.empty()){P current que.top();que.pop();if (used[current.second] || current.first d[current.second]){continue;}used[current.second] true;for (int i 0; i edges[current.second].size(); i){P toEdge edges[current.second][i];if (d[current.second] toEdge.first d[toEdge.second]){d[toEdge.second] d[current.second] toEdge.first;que.push(P(d[toEdge.second], toEdge.second));}}}return d[n - 1] ! inf;
}
int main()
{input();if (!judgeIfCanGet()){printf(-1\n);}else{binarySearch();}return 0;
}
